ms$ ghc unesl.hs

ms$ ./unesl

$> :load toPost.nesl    -- :l doesn't work
Defined even_elts : @a.([a]) -> [a]
Defined odd_elts : @a.([a]) -> [a]
Defined interleave : @a.([a], [a]) -> [a]
Defined bottop : @a.([a]) -> [[a]]
Defined last : @a.([a]) -> a
Defined reverse : @a.([a]) -> [a]
Defined scan_op : @a.((a, a) -> a, a, [a]) -> [a]
Defined scan12 : @a.((a, a) -> a, a, [a]) -> [a]
Defined sklansky : @a.((a, a) -> a, [a]) -> [a]
Defined bitonic_sort : @#a.([a]) -> [a]
Defined batcher_sort : @#a.([a]) -> [a]

-- I write comments like this

-- Now just type in applications of functions to input at the prompt

-- &n gives the array contining 0..(n-1)
$> &8
[0, 1, 2, 3, 4, 5, 6, 7] : [int]
[Work: 8, span: 1]

$> reverse(&8)
[7, 6, 5, 4, 3, 2, 1, 0] : [int]
[Work: 41, span: 5]

$> reverse([1,3,2])
[2, 3, 1] : [int]
[Work: 17, span: 5]


$> reverse(&8)
[7, 6, 5, 4, 3, 2, 1, 0] : [int]
[Work: 41, span: 5]




$> sklansky(_plus,&16)
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120] : [int]
[Work: 368, span: 54]

$> sklansky(_plus,&17)
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136] : [int]
[Work: 393, span: 67]




$> scan12(_plus,0,&16)
[0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105] : [int]
[Work: 193, span: 51]

-- scan12 works only for input length a power of two. Runtime error otherwise.
$> scan12(_plus,0,&17)
Runtime error: In "toPost.nesl" (line 37, column 14): partition: length mismatch





-- This is the bitonic merger. And the input is not bitonic. Output not sorted
$> bitonic_sort(&8++&8)
[0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7] : [int]
[Work: 566, span: 72]

-- This input is bitonic. So the merger produces sorted output.
$> bitonic_sort(&8 ++ reverse(&8))
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7] : [int]
[Work: 599, span: 76]

-- But the sorter works on unsorted input (of length a power of two)
$> batcher_sort(&8++&8)
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7] : [int]
[Work: 2093, span: 230]

-- See how work and span vary with size of input
$> batcher_sort(&16 ++ &16)
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15] : [int]
[Work: 5453, span: 329]


$> :quit
Bye!