Benchmark Program

The following program is the benchmark Isort (in KiR notation). A few explanations for those parts that are not obvious: Operations on binary lists: o concatenation, hd head, tl tail. Operations on n-ary lists: ++ unite, lselect(n,L) select the n-th element of list L. <> denotes an empty list (binary as well as n-ary).

def 
  Map[ F, L ] = if empty( L )
     then <>
     else o F[ hd( L ) ] Map[ F, tl( L ) ],
  Insert[ N, T ] = if empty( T )
     then o N <>
     else let M = hd( T )
          in if ( N lt M )
             then o N T
             else o M Insert[ N, tl( T ) ],
  Count[ X, Y ] = if ( X gt Y )
     then <>
     else o X Count[ ( X + 1 ), Y ],
  Sort[ L ] = if empty( L )
     then L
     else Insert[ hd( L ), Sort[ tl( L ) ] ],
  Rand[ R ] = ( ( 56789 * R ) mod 12345 )
in Sort[ Map[ Rand, Count[ 1, 100 ] ] ]

The following program is the benchmark Treesort.

def 
  Map[ F, L ] = if empty( L )
     then <>
     else o F[ hd( L ) ] Map[ F, tl( L ) ],
  Reduce[ Op, L, N ] = if empty( L )
     then N
     else ( hd( L ) Op Reduce[ Op, tl( L ), N ] ),
  Insert[ N, T ] = if empty( T )
     then < <>, N, <> >
     else let M = lselect( 2, T )
          in if ( N lt M )
             then < Insert[ N, lselect( 1, T ) ], M
                           , lselect( 3, T ) >
             else < lselect( 1, T ), M
                           , Insert[ N, lselect( 3, T ) ] >,
  Flatten[ T ] = if empty( T )
     then <>
     else ( Flatten[ lselect( 1, T ) ] ++ ( < lselect( 2, T ) >
                      ++ Flatten[ lselect( 3, T ) ] ) ),
  Sort[ Lis ] = Flatten[ Reduce[ Insert, Lis, <> ] ],
  Count[ X, Y ] = if ( X gt Y )
     then <>
     else o X Count[ ( X + 1 ), Y ],
  Rand[ R ] = ( ( 56789 * R ) mod 12345 )
in Sort[ Map[ Rand, Count[ 1, 100 ] ] ]