December 2010 - Haskell-Cafe

Fibonacci Heap without using Monad
by larry.liuxinyu 30 Dec '10

30 Dec '10

Hi, I checked the current Fibonacci Queue in Hackage DB: http://hackage.haskell.org/packages/archive/pqueue-mtl/1.0.7/doc/html/src/D… And a history email for Okasaki in 1995: http://darcs.haskell.org/nofib/gc/fibheaps/orig The hardest part is how to consolidate all unordered binomial trees in deleteMin. In imperative implementation, there is a elegant algorithm introduced in Chapter 20 of CLRS[1]. How to achieve it in Functional way is the key point of solve this problem. If we have a list of trees with rank [2, 1, 1, 4, 8, 1, 1, 2, 4], we need first meld the trees with same rank, and recursively doing that until there are no two trees with same rank. Here is a simple function can do this: consolidate:: (Num a)=>[a] -> [a] consolidate xs = foldl meld [] xs where meld :: (Num a)=>[a] -> a -> [a] meld [] x = [x] meld (x':xs) x = if x == x' then meld xs (x+x') else x:x':xs Generalize the `+` to link and `==` to compare rank yields the solution. Below are my literate source code with some description. For the details of Binomial heap, please refer to Okasaki's ``Purely Functional data structures''[2]. -- Definition -- Since Fibonacci Heap can be achieved by applying lazy strategy -- to Binomial heap. We use the same definition of tree as the -- Binomial heap. That each tree contains: -- a rank (size of the tree) -- the root value (the element) -- and the children (all sub trees) data BiTree a = Node { rank :: Int , root :: a , children :: [BiTree a]} deriving (Eq, Show) -- Different with Binomial heap, Fibonacci heap is consist of -- unordered binomial trees. Thus in order to access the -- minimum value in O(1) time, we keep the record of the tree -- which holds the minimum value out off the other children trees. -- We also record the size of the heap, which is the sum of all ranks -- of children and minimum tree. data FibHeap a = E | FH { size :: Int , minTree :: BiTree a , trees :: [BiTree a]} deriving (Eq, Show) -- Auxiliary functions -- Singleton creates a leaf node and put it as the only tree in the heap singleton :: a -> FibHeap a singleton x = FH 1 (Node 1 x []) [] -- Link 2 trees with SAME rank R to a new tree of rank R+1, we re-use the code -- for Binomial heaps link :: (Ord a) => BiTree a -> BiTree a -> BiTree a link t1@(Node r x c1) t2@(Node _ y c2) | x<y = Node (r+1) x (t2:c1) | otherwise = Node (r+1) y (t1:c2) -- Insertion, runs in O(1) time. insert :: (Ord a) => FibHeap a -> a -> FibHeap a insert h x = merge h (singleton x) -- Merge, runs in O(1) time. -- Different from Binomial heap, we don't consolidate the sub trees -- with the same rank, we delayed it later when performing delete- Minimum. merge:: (Ord a) => FibHeap a -> FibHeap a -> FibHeap a merge h E = h merge E h = h merge h1@(FH sz1 minTr1 ts1) h2@(FH sz2 minTr2 ts2) | root minTr1 < root minTr2 = FH (sz1+sz2) minTr1 (minTr2:ts2+ +ts1) | otherwise = FH (sz1+sz2) minTr2 (minTr1:ts1++ts2) -- Find Minimum element in O(1) time findMin :: (Ord a) => FibHeap a -> a findMin = root . minTree -- deleting, Amortized O(lg N) time -- Auxiliary function -- Consolidate unordered Binomial trees by meld all trees in same rank -- O(lg N) time consolidate :: (Ord a) => [BiTree a] -> [BiTree a] consolidate ts = foldl meld [] ts where meld [] t = [t] meld (t':ts) t = if rank t' == rank t then meld ts (link t t') else t:t':ts -- Find the tree which contains the minimum element. -- Returns the minimum element tree and the left trees as a pair -- O(lg N) time extractMin :: (Ord a) => [BiTree a] -> (BiTree a, [BiTree a]) extractMin [t] = (t, []) extractMin (t:ts) = if root t < root t' then (t, ts) else (t', t:ts') where (t', ts') = extractMin ts -- delete function deleteMin :: (Ord a) => FibHeap a -> FibHeap a deleteMin (FH _ (Node _ x []) []) = E deleteMin h@(FH sz minTr ts) = FH (sz-1) minTr' ts' where (minTr', ts') = extractMin $ consolidate (children minTr ++ ts) -- Helper functions fromList :: (Ord a) => [a] -> FibHeap a fromList xs = foldl insert E xs -- general heap sort function, can be re-used for any heap heapSort :: (Ord a) => [a] -> [a] heapSort = hsort . fromList where hsort E = [] hsort h = (findMin h):(hsort $ deleteMin h) -- test testFromList = fromList [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] testHeapSort = heapSort [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] Below are the test results in GHC. *FibonacciHeap> testFromList FH {size = 10, minTree = Node {rank = 1, root = 1, children = []}, trees = [Node {rank = 1, root = 2, children = []},Node {rank = 1, root = 4, children = []},Node {rank = 1, root = 3, children = []},Node {rank = 1, root = 7, children = []},Node {rank = 1, root = 9, children = []},Node {rank = 1, root = 8, children = []},Node {rank = 1, root = 10, children = []},Node {rank = 1, root = 14, children = []},Node {rank = 1, root = 16, children = []}]} *FibonacciHeap> testHeapSort [1,2,3,4,7,8,9,10,14,16] -- [1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein ``Introduction to Algorithms, Second Edition'. The MIT Press © 2001 (1180 pages) ISBN: [2] Chris Okasaki. ``Purely Functional Data Structures''. Cambridge university press, (July 1, 1999), ISBN-13: 978-0521663502

1 2

"record" types and unique names
by Aaron Gray 30 Dec '10

30 Dec '10

Given a Haskell "record type" :- data Test = Test { name :: String, value :: Int } test = Test { name = "test", value = 1 } main :: IO () main = do putStrLn (name test) Are "name" and "value" in the global name space, as the following gives an error "Multiple declarations of `name'" :- name :: String -> String name s = s Is there any way round this ? Many thanks in advance, Aaron

3 5

Not in scope: type constructor or class `Map'
by michael rice 30 Dec '10

30 Dec '10

Not sure what's going on here. Doesn't like line 5, the type statement. And what's with the semicolons in that line and in function main? Michael ========= From: http://www.haskell.org/ghc/docs/6.10.3/html/libraries/mtl/Control-Monad-Rea… import Control.Monad.Reader import qualified Data.Map as Map import Data.Maybe type Bindings = Map String Int; -- Returns True if the "count" variable contains correct bindings size. isCountCorrect :: Bindings -> Bool isCountCorrect bindings = runReader calc_isCountCorrect bindings -- The Reader monad, which implements this complicated check. calc_isCountCorrect :: Reader Bindings Bool calc_isCountCorrect = do count <- asks (lookupVar "count") bindings <- ask return (count == (Map.size bindings)) -- The selector function to use with 'asks'. -- Returns value of the variable with specified name. lookupVar :: String -> Bindings -> Int lookupVar name bindings = fromJust (Map.lookup name bindings) sampleBindings = Map.fromList [("count",3), ("1",1), ("b",2)] main = do putStr $ "Count is correct for bindings " ++ (show sampleBindings) ++ ": "; putStrLn $ show (isCountCorrect sampleBindings); ========== Prelude> :l monad5 [1 of 1] Compiling Main ( monad5.hs, interpreted ) monad5.hs:5:16: Not in scope: type constructor or class `Map' Failed, modules loaded: none.

3 3

";" in do
by Daryoush Mehrtash 30 Dec '10

30 Dec '10

Why do people put ";" in do {}, or "," in data fields, at the beginning of the line? -- Daryoush Weblog: http://onfp.blogspot.com/

9 14

Incorrectly inferring type [t]
by william murphy 30 Dec '10

30 Dec '10

Hi All, I've spent a lot of time trying to write a version of concat, which concatenates lists of any "depth": So: concat'' [[[1,2],[3,4]],[[5]]] would return: [1,2,3,4,5] The code is: concat'' :: [a] -> [b] concat'' ((y:ys):xs) = (concat'' (y:ys)) ++ (concat'' xs) concat'' [] = [] concat'' (x:xs) = (x:xs) And the inevitable error is: test.hs:298:12: Couldn't match expected type `a' against inferred type `[t]' `a' is a rigid type variable bound by the type signature for `concat''' at test.hs:297:13 In the pattern: y : ys In the pattern: (y : ys) : xs In the definition of `concat''': concat'' ((y : ys) : xs) = (concat'' (y : ys)) ++ (concat'' xs) test.hs:300:24: Couldn't match expected type `b' against inferred type `[t]' `b' is a rigid type variable bound by the type signature for `concat''' at test.hs:297:20 In the first argument of `(:)', namely `x' In the expression: (x : xs) In the definition of `concat''': concat'' (x : xs) = (x : xs) Failed, modules loaded: none. Any help or advice would be appreciated. Will

4 3

Lambda Calculus: Bound and Free formal definitions
by Mark Spezzano 30 Dec '10

30 Dec '10

Hi, Presently I am going through AJT Davie's text "An Introduction to Functional Programming Systems Using Haskell". On page 84, regarding formal definitions of FREE and BOUND variables he gives Defn 5.2 as The variable X is free in the expression E in the following cases a) <omitted> b) If E is a combination E1 E2 then X is free in E if and only if X is free in E1 or X is free in E2 c) <omitted> Then in Defn 5.3 he states The variable X is bound in the expression E in the following cases a) <omitted> b) If E is a combination E1 E2 then X is free in E if and only if X is free in E1 or X is free in E2. c) <omitted> Now, are these definitions correct? They seem to contradict each other....and they don't make much sense on their own either (try every combination of E1 and E2 for bound and free and you'll see what I mean). If it is correct then please give some examples of E1 and E2 showing exactly why. Personally I think that there's an error in the book. You can see the full text on Google Books (page 84) Thanks for reading! Mark Spezzano

8 8

SampleVar semantics, documentation vs. source
by Eric Stansifer 30 Dec '10

30 Dec '10

Hi, doc: http://www.haskell.org/ghc/docs/7.0-latest/html/libraries/base-4.3.0.0/Cont… source: http://www.haskell.org/ghc/docs/7.0-latest/html/libraries/base-4.3.0.0/src/… The documentation for Control.Concurrent.SampleVar implies that a SampleVar is either "filled" or "empty". The source code suggests that there are three possible states: "full" (when readers == 1), "empty" (when readers == 0), and "empty with blocked readers" (when readers < 0). In particular, the isEmptySampleVar function, isEmptySampleVar :: SampleVar a -> IO Bool isEmptySampleVar (SampleVar svar) = do (readers, _) <- readMVar svar return (readers == 0) returns false in the third state, when readers < 0. Can someone clarify the semantics of SampleVar? Thanks, Eric

1 0

what is the status of haskell's mail libraries?
by Günther Schmidt 29 Dec '10

29 Dec '10

Hi all, I was just looking for mail libraries on hackage. You know libraries where I can construct an email, or retrieve on from the server. With retrieving an email I mean something with a bit more structure than a String, or, God help me, a ByteString. Where are we on this subject? I really cannot tell from the first glance. Günther

5 8

How to make such code?
by Magicloud Magiclouds 29 Dec '10

29 Dec '10

Hi, In Haskell's way, normally, we write: if condition then expression_true else expression_false But I just heard that, in fancy way, we could do: do ifNeedToDo >> doIt bluh May I have any clue here? -- 竹密岂妨流水过山高哪阻野云飞

2 1

Re: [Haskell-cafe] [Haskell-beginners] Tying the knot
by Antoine Latter 29 Dec '10

29 Dec '10

On Wed, Dec 29, 2010 at 7:22 PM, aditya siram <aditya.siram(a)gmail.com> wrote: > My brain turns into strange braid when I see this kind of thing. I > don't quite understand it and I've never used it in real world code > but I'll try and explain anyway. Caveat emptor. > Once when I was parsing a group of source files into an AST, the source files included 'copy' directives that allowed pieces of syntax to be a clone of some other piece of syntax - even across source files. So I did the whole process of parsing in the Reader monad, which was parametrized over the result of parsing all of the files. When I hit a copy directive, I simply called 'ask' and looked up the element I wanted to copy. It doesn't allow for separate processing of source files, but I didn't really need it. Antoine > First forget about 'labelLeaves' and think a function that only > returned the leaf count: > count :: Tree a -> Int > count tree = c > where > c = count' tree > > count' (Branch a b) = na+nb > where > na = count' a > nb = count' b > count' (Leaf _) = 1 > >> count $ Branch (Leaf "hello") (Leaf "world") > 2 > > Now look at 'n' and imagine it was a memory location. Mentally > substitute some hex address (like 0x0000) if it makes it easier. > Here's what the function looks like now: > > labelLeaves :: Tree a -> Tree Int > labelLeaves tree = tree' > where > (0x0000, tree') = label 0x0000 tree -- n is both result and argument! > > label 0x0000 (Branch a b) = (na+nb, Branch a' b') > where > (na,a') = label 0x0000 a > (nb,b') = label 0x0000 b > label 0x0000 (Leaf _) = (1, Leaf 0x0000) > > So if labelLeaves is given (Branch (Leaf "hello") (Leaf "world")) as > an argument, and we continue to think of 'n' as a memory location the > function returns something like: > (Branch (Leaf 0x0000) (Leaf 0x0000)) > > The part of the function where the leaves are counted up is exactly > like my 'count' example above, but when the function is done instead > of just returning it this line: > (n,tree') = label n tree > assigns the final count to 'n'. If 'n' is a memory location the final > leaf count would be sitting in 0x0000. Subbing the value at that > location into the result we get: > (Branch (Leaf 2) (Leaf 2)) > > > -deech > > On Wed, Dec 29, 2010 at 4:52 PM, Patrick LeBoutillier > <patrick.leboutillier(a)gmail.com> wrote: >> Heinrich, >> >>> A canonical example is the following solution to the problem of labeling all >>> the leaves in a tree with the total leaf count: >>> >>> data Tree a = Branch (Tree a) (Tree a) | Leaf a >>> >>> labelLeaves :: Tree a -> Tree Int >>> labelLeaves tree = tree' >>> where >>> (n, tree') = label n tree -- n is both result and argument! >>> >>> label n (Branch a b) = (na+nb, Branch a' b') >>> where >>> (na,a') = label n a >>> (nb,b') = label n b >>> label n (Leaf _) = (1, Leaf n) >>> >> >> This looks completely freaky to me... how does it work? Is it the >> laziness that allows the sum to be calculated first while preserving >> the structure (as thunks?), and then once the value of n is known it >> is propagated back down the tree and the actual tree values >> constructed? Anyways this is really amazing to my newbie eyes... >> >> Patrick >> -- >> ===================== >> Patrick LeBoutillier >> Rosemère, Québec, Canada >> >> _______________________________________________ >> Beginners mailing list >> Beginners(a)haskell.org >> http://www.haskell.org/mailman/listinfo/beginners >> > > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners >

1 0