News aggregator

Jeremy Gibbons: Breadth-First Traversal

Planet Haskell - Sun, 03/15/2015 - 11:00am

Recently Eitan Chatav asked in the Programming Haskell group on Facebook

What is the correct way to write breadth first traversal of a ?

He’s thinking of “traversal” in the sense of the class, and gave a concrete declaration of rose trees:

It’s an excellent question.

Breadth-first enumeration

First, let’s think about breadth-first enumeration of the elements of a tree. This isn’t compositional (a fold); but the related “level-order enumeration”, which gives a list of lists of elements, one list per level, is compositional:

Here, is “long zip with”; it’s similar to , but returns a list as long as its longer argument:

(It’s a nice exercise to define a notion of folds for , and to write as a fold.)

Given , breadth-first enumeration is obtained by concatenation:

Incidentally, this allows trees to be foldable, breadth-first:


Level-order enumeration is invertible, in the sense that you can reconstruct the tree given its shape and its level-order enumeration.

One way to define this is to pass the level-order enumeration around the tree, snipping bits off it as you go. Here is a mutually recursive pair of functions to relabel a tree with a given list of lists, returning also the unused bits of the lists of lists.

Assuming that the given list of lists is “big enough”—ie each list has enough elements for that level of the tree—then the result is well-defined. Then is determined by the equivalence

Here, the of a tree is obtained by discarding its elements:

In particular, if the given list of lists is the level-order of the tree, and so is exactly the right size, then will have no remaining elements, consisting entirely of empty levels:

So we can take a tree apart into its shape and contents, and reconstruct the tree from such data.

Breadth-first traversal

This lets us traverse a tree in breadth-first order, by performing the traversal just on the contents. We separate the tree into shape and contents, perform a list-based traversal, and reconstruct the tree.

This trick of traversal by factoring into shape and contents is explored in my paper Understanding Idiomatic Traversals Backwards and Forwards from Haskell 2013.

Inverting breadth-first enumeration

We’ve seen that level-order enumeration is invertible in a certain sense, and that this means that we perform traversal by factoring into shape and contents then traversing the contents independently of the shape. But the contents we’ve chosen is the level-order enumeration, which is a list of lists. Normally, one thinks of the contents of a data structure as simply being a list, ie obtained by breadth-first enumeration rather than by level-order enumeration. Can we do relabelling from the breadth-first enumeration too? Yes, we can!

There’s a very clever cyclic program for breadth-first relabelling of a tree given only a list, not a list of lists; in particular, breadth-first relabelling a tree with its own breadth-first enumeration gives back the tree you first thought of. In fact, the relabelling function is precisely the same as before! The trick comes in constructing the necessary list of lists:

Note that variable is defined cyclically; informally, the output leftovers on one level also form the input elements to be used for relabelling all the lower levels. Given this definition, we have

for any . This program is essentially due to Geraint Jones, and is derived in an unpublished paper Linear-Time Breadth-First Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips that we wrote together in 1993.

We can use this instead in the definition of breadth-first traversal:

Categories: Offsite Blogs

Getting Into Netwire

Haskell on Reddit - Sun, 03/15/2015 - 5:32am
Categories: Incoming News

chat #haskell

Haskell on Reddit - Sun, 03/15/2015 - 5:05am
Categories: Incoming News

Wrong .hsc file paths on Windows

haskell-cafe - Sat, 03/14/2015 - 9:08pm
Hello, I was trying to port some of my code to Windows. I've installed GHC with MinGHC ( Unfortunately some packages, namely zlib and network, won't install, with the same error: getModificationTime cannot locate a file like CodecCompressionZlibStream.hsc or NetworkSocketTypes.hsc. With zlib, I figured out I just need to change mentions of "Codec/Compression/(...)" adding two slashes instead of one. Now with network I'm stuck, I can't find where the path was set at all. Is there some step I should have done prior to installation that would get the paths right? Best regards, Marcin Mrotek
Categories: Offsite Discussion


haskell-cafe - Sat, 03/14/2015 - 11:23am
Happy super pi day everybody! Henk-Jan van Tuyl
Categories: Offsite Discussion

repa parallelization results

haskell-cafe - Fri, 03/13/2015 - 6:23pm so i am seeing basically results with N4 that are as good as using sequential computation on my macbook for the matrix multiply algorithm. any idea why? Thanks, Anatoly
Categories: Offsite Discussion

Generalizing map?

libraries list - Fri, 03/13/2015 - 10:32am
A dozen of functions like concat, foldr, mapM, have been generalized through BBP. Then, why do we leave `map` just for lists? Obviously `map` can be generalized, so map :: Functor f => (a -> b) -> f a -> f b map = fmap The current definition of `map` looks too special to be a special case of mapM (map f = runIdentity . mapM (Identity . f)). _______________________________________________ Libraries mailing list Libraries< at >
Categories: Offsite Discussion

Proposal: Export cycleN from Data.Sequence

libraries list - Wed, 03/11/2015 - 4:14pm
Yesterday I rewrote `*>` for Data.Sequence (again), using an internal function cycleN :: Int -> Seq a -> Seq a The name of the function is based on that of Data.Sequence.iterateN. cycleN takes a sequence and cycles it as many times as requested: cycleN 0 $ fromList [1,2] = [] cycleN 5 $ fromList [1,2] = [1,2,1,2,1,2,1,2,1,2] The function is written to maximize sharing in the result sequence and to minimize construction time. Specifically, cycleN n xs should take something like O(|xs| + log n) space (of which all but O(log |xs| + log n) is shared with the structure of xs) and O(log |xs| + log n) time. With current (on GitHub) Data.Sequence exports, the only way to get this functionality with these time and space bounds is to combine replicate with *> : cycleN n xs = replicate n () *> xs This strikes me as a bit unpleasant. David
Categories: Offsite Discussion

-staticlib flag for building standalone static libraries producing very large libraries

glasgow-user - Sat, 03/07/2015 - 1:18pm
Hi all, Can anyone explain the following problem I'm having? I'm currently writing a game in Haskell. When I produce a plain old executable (for local testing) it's about 23M. However, when I create a static lib using the -staticlib flag it is 54M. Why the discrepancy? Sean _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users< at >
Categories: Offsite Discussion

New gtk2hs 0.12.4 release

gtk2hs - Wed, 11/21/2012 - 12:56pm

Thanks to John Lato and Duncan Coutts for the latest bugfix release! The latest packages should be buildable on GHC 7.6, and the cairo package should behave a bit nicer in ghci on Windows. Thanks to all!


Categories: Incoming News