On 05/09/2011 09:52 AM, Invisible wrote:

> ...or maybe I'm just delusional from having spent too long with Haskell?

Trivial program... is trivial.

It seems everybody agrees on that. Now let's try the sort of code that 
typically appears in an introductory Haskell textbook:

   module Heap
       (
         MinHeap (), empty, is_empty,
         top, insert, delete_top,
         union, size, to_list, from_list, heap_sort
       )
     where

   data MinHeap x = Leaf | Node x (MinHeap x) (MinHeap x)

   empty :: MinHeap x
   empty = Leaf

   is_empty :: MinHeap x -> Bool
   is_empty Leaf = True
   is_empty _    = False

   top :: MinHeap x -> x
   top (Leaf      ) = error "empty heap"
   top (Node x _ _) = x

   insert :: Ord x => x -> MinHeap x -> MinHeap x
   insert x' (Leaf        ) = Node x' Leaf Leaf
   insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0

   delete_top :: Ord x => MinHeap x -> MinHeap x
   delete_top (Leaf        ) = error "empty heap"
   delete_top (Node _ h0 h1) = union h0 h1

   union :: Ord x => MinHeap x -> MinHeap x -> MinHeap x
   union h0 h1 =
     case (h0, h1) of
       (Leaf, _   ) -> h1
       (_   , Leaf) -> h0
       (_   , _   ) ->
         if top h0 < top h1
           then Node (top h0) h1 (delete_top h0)
           else Node (top h1) h0 (delete_top h1)

   size :: MinHeap x -> Int
   size (Leaf        ) = 0
   size (Node _ h0 h1) = 1 + size h0 + size h1

   to_list :: Ord x => MinHeap x -> [x]
   to_list (Leaf        ) = []
   to_list (Node x h0 h1) = x : to_list (union h0 h1)

   from_list :: Ord x => [x] -> MinHeap x
   from_list = foldr insert empty

   heap_sort :: Ord x => [x] -> [x]
   heap_sort = to_list . from_list

(This one - or something resembling it - appears in "The Fun of 
Programming", Jeremy Gibbons & Oege de Moor, Palgrave Macmillan, in 
chapter 1. Then again, strictly this isn't a book about learning 
Haskell. It's about functional programming in general - as best as I can 
tell...)

This is classic functional programming. The only thing missing is that 
there's no high-order functions or type-level programming. It's got just 
about everything else. Now let's see if Warp's claims hold up.

While the identifier names are strongly suggestive, I doubt anybody not 
mildly fuent in Haskell is going to figure out what's actually going on 
here. I'll post a Java translation in a minute. Then we can see whether 
the program becomes clearer (i.e., Haskell is the problem) or remains 
opaque (i.e., the algorithm is the problem).

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message