April 2009 - Haskell-Cafe

Re: [Haskell-beginners] Re: making translation from imperative code
by Michael Mossey 02 Apr '09

02 Apr '09

Thanks very much for the help... I will look at this over the next couple of days. Your code actually addresses a different problem, the one of merging separates lists of timed events. I do need to write code to do that eventually, so I will try to understand what you have written here. However, the original problem concerns visual layout, which actually takes place *after* creating a merged list. In layout, items do have times associated with them, but also take up physical space. Different items takes up different amounts of space, and at any given "time," there may be items on all the staves or just some of them. I will try to come up with (1) a more succinct explanation of the problem (with textual graphics as a visual aid) (2) a more succinct algorithm. For example, you are right that I'm mixing concerns. The system layout can terminate for two reasons: (1) reached the end of the score (2) reached the right edge of the page. There might be a way to simplify the loop or fold so that these concerns look more unified. -Mike PS a question below: Heinrich Apfelmus wrote: > Michael Mossey wrote: >> Heinrich Apfelmus wrote: >>> Can you elaborate on what exactly the algorithm is doing? Does it just >>> emit notes/chords/symbols at given positions or does it also try to >>> arrange them nicely? And most importantly, "where" does it emit them to, >>> i.e. what's the resulting data structure? >>> >>> So far, the problem looks like a basic fold to me. >> Here is some Haskell code that explains the problem in >> more detail. >> [...] > > Thanks for the elaboration. > > I think the code doesn't separate concerns very well; mixing information > about widths and times, page size and the recursion itself into one big > gnarl. > > Also, there is one important issue, namely returning a special value > like -1 as error code in > >> tryAgain state = >> case scoreNextTime score (time state) of >> -1 -> indicateNoMoreChunks state >> t -> layoutSystem' (setTime state t) > > Don't do this, use Maybe instead > > tryAgain state = case scoreNextTime score (time state) of > Nothing -> indicateNoMoreChunks state > Just t -> layoutSystem' (state { time = t }) > > where Nothing indicates failure and Just success. > > > Back to the gnarl in general, I still don't have a good grasp on the > problem domain, which is key to structuring the algorithm. Therefore, > I'll expand on toy model and you tell me how it differs from the real thing. > > The model is this: we are given several lists of notes (f.i. a piano > part and a vocal line) where each note is annotated with the time it is > to be played at. We abstract away the fact that we are dealing with > musical notes and simply consider a list of *events* > > type Time = Integer > type Events a = [(Time, a)] > > with the invariant that the timestamps are (strictly) increasing: > > valid :: Events a -> Bool > valid xs = all $ zipWith (\(t1,_) (t2,_) -> t1 < t2) xs (drop 1 xs) > > Now, the toy task is to merge several lists of similar events into one > big list that is ordered by time as well. > > merge :: [Events a] -> Events [a] > > Since some events may now occur simultaneously, the events of the > results are actually lists of "primitive" events. > > One possibility for implementing merge is to start with a function to > merge two event lists > > merge2 :: Events [a] -> Events [a] -> Events [a] > merge2 [] ys = ys > merge2 xs [] = xs > merge2 xs@((tx,x):xt) ys@((ty,y):yt) = case compare tx ty of > LT -> (tx,x ) : merge2 xt ys > EQ -> (tx,x++y) : merge2 xt yt > GT -> (ty, y) : merge2 xs yt > > and to apply it several times > > merge = foldr merge2 [] . map lift > where lift = map $ \(t,x) -> (t,[x]) > > > Another possibility is to simply concatenate everything first and then > sort by time > > merge = map (\((t,x):xs) -> (t,x:map snd xs)) > . groupBy ((==) `on` fst) > . sortBy (comparing fst) > . concat > > > The code above can be made more readable by choosing nice names like > > time = fst > event = snd > > or avoiding pairs altogether and implementing these names as record > fields. Also, the (&&&) combinator from Control.Arrow is very handy. > > merge = map (time . head &&& map event) > . groupBy ((==) `on` time) > . sortBy (comparing time) > . concat > > > I hope this gives you a few ideas to think about. How does this toy > model differ from the real thing? > > > Regards, > apfelmus > > > PS: If some parts of my example code give you trouble, it's probably > fastest to ask around on the #haskell IRC channel. > > -- > http://apfelmus.nfshost.com > > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners

1 0

GSoC proposal
by Csaba Hruska 02 Apr '09

02 Apr '09

Hi! I've submitted my proposal on gsoc portal. (3D Rendering Engine) What's your opinion?

4 5

Leksah patch release 0.4.4.1
by Jürgen Nicklisch-Franken 01 Apr '09

01 Apr '09

I've pushed a patch with a minor fix for the recurring query to open a file: * Doesn't attempt a background build, when there is no open package. * Doesn't keep bugging the user if the session they select does not have a valid package * Improved title on package open dialog * Updated the manual for better Ubuntu installation description Please note that Leksah doesn't work with GHC version 6.10.2 currently, because gtk2hs has problems with the changes on finalizers. Hope they can fix this soon. Jürgen

1 0

ANNOUNCE: vacuum: extract graph representations of ghc heap values.
by Matt Morrow 01 Apr '09

01 Apr '09

I am pleased to announce the release of vacuum, a Haskell<http://haskell.org/>library for extracting graph representations of values from the GHC <http://haskell.org/ghc/> heap, which may then be further processed and/or translated to Graphviz <http://graphviz.org/> dot format to be visualized. The package website is at http://moonpatio.com/vacuum/, which contains a gallery section (which i intend to add to over time). The most recent version is 0.0.6, which is available on Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vacuum/. Feedback, comments, and/or gallery submissions will be gratefully received via this email address (contrary to the email address currently on the vacuum Hackage page (i fail at setting up email :)). Matt

2 2

Re: [Haskell-cafe] uvector package appendU: memory leak?
by Manlio Perillo 01 Apr '09

01 Apr '09

wren ng thornton ha scritto: > Manlio Perillo wrote: >> Since ratings for each customers are parsed "at the same time", using >> a plain list would consume a lot of memory, since stream fusion can >> only be executed at the end of the parsing. >> >> On the other hand, when I want to group ratings by movies, stream >> fusion seems to work fine. >> > [...] > > For the problem as you've discussed it, I'd suggest a different > approach: You can't fit all the data into memory at once, so you > shouldn't try to. You should write one program that takes in the > per-movie grouping of data and produces a per-user file as output. Well, creating 480189 files in a directory is not a very nice thing to do to a normal file system. I should arrange files in directory, but then this starts to become too complex. The solution I'm using now just works. It takes about 950 MB of memory and 35 minutes, but it's not a big problem since: 1) Once loaded, I can serialize the data in binary format 2) I think that the program can be parallelized, parsing subsets of the files in N threads, and then merging the maps. Using this method, should optimize array copying. The problem is that unionWith seems to be lazy, and there is no no strict variant; I'm not sure. > Then > have your second program read in the reorganized data and do fusion et al. > > This reduces the problem to just writing the PerMovie -> PerUser > program. Since you still can't fit all the data into memory, that means > you can't hope to write the per-user file in one go. The data *do* fit into memory, fortunately. > [...] > > Best of luck. > Thanks Manlio

2 1

Zippers from any traversable [Was: Looking for practical examples of Zippers]
by oleg＠okmij.org 01 Apr '09

01 Apr '09

wren ng thornton wrote: > > how, for instance, turn a nested Map like > > > > Map Int (Map Int (Map String Double) > > > > into a "zipped" version. > You can't. Or rather, you can't unless you have access to the > implementation of the datastructure itself; and Data.Map doesn't provide > enough details to do it. Actually Data.Map does provide enough details: Data.Map is a member of Traversable and anything that supports Traversable (at the very least, provides something like mapM) can be turned into a Zipper. Generically. We do not need to know any details of a data structure (or if it is a data structure: the collection may well be ephemeral, whose elements are computed on the fly). Please see the enclosed code; the code defines a function tmod to interactively traverse the collection, displaying the elements one by one and offering to modify the current element, or quit the traversal. The enclosed code implements the zipper that can only move forward. Chung-chieh Shan has well described how to turn any one-directional zipper into bi-directional. Again generically. http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip3/ Although the enclosed code demonstrates the possibility of turning a Data.Map into a Zipper, one may wonder about the merits of that endeavour. Data.Map is a very rich data structure, with efficient means to focus on any given element and replace it (e.g., elemAt, replaceAt) and to incrementally deconstruct the map (deleteMax, deleteMin, minView, etc). Triple-nested maps can be processed just as effectively. The case for a tree of maps (which is essentially a file system) is described in http://okmij.org/ftp/Computation/Continuations.html#zipper-fs module ZT where import qualified Data.Traversable as T import Control.Monad.Cont import qualified Data.Map as M -- In the variant Z a k, a is the current, focused value -- evaluate (k Nothing) to move forward -- evaluate (k v) to replace the current value with v and move forward. data Zipper t a = ZDone (t a) | Z a (Maybe a -> Zipper t a) make_zipper :: T.Traversable t => t a -> Zipper t a make_zipper t = reset $ T.mapM f t >>= return . ZDone where f a = shift (\k -> return $ Z a (k . maybe a id)) zip_up :: Zipper t a -> t a zip_up (ZDone t) = t zip_up (Z _ k) = zip_up $ k Nothing reset :: Cont r r -> r reset m = runCont m id shift :: ((a -> r) -> Cont r r) -> Cont r a shift e = Cont (\k -> reset (e k)) -- Tests -- sample collections tmap = M.fromList [ (v,product [1..v]) | v <- [1..10] ] -- extract a few sample elements from the collection trav t = let (Z a1 k1) = make_zipper t (Z a2 k2) = k1 Nothing (Z a3 k3) = k2 Nothing (Z a4 k4) = k3 Nothing in [a1,a3,a4] travm = trav tmap -- Traverse and possibly modify elements of a collection tmod t = loop (make_zipper t) where loop (ZDone t) = putStrLn $ "Done\n: " ++ show t loop (Z a k) = do putStrLn $ "Current element: " ++ show a ask k ask k = do putStrLn "Enter Return, q or the replacement value: " getLine >>= check k check k "" = loop $ k Nothing check k "\r" = loop $ k Nothing check k ('q':_) = loop . ZDone . zip_up $ k Nothing check k s | [(n,_)] <- reads s = loop $ k (Just n) -- replace check k _ = putStrLn "Repeat" >> ask k testm = tmod tmap

2 1

Parsing with Proof
by muad 01 Apr '09

01 Apr '09

Hi everyone on haskell-cafe, I am wondering about how to give a correctness prove of a simple parsing algorithm. I tried to think of a simple example but even in this case I don't know how. I have an abstract syntax: > data Parens = Empty | Wrap Parens | Append Parens Parens assumption (A), in Append x y, x and y are never Empty assumption (B), Strings only contain '(' and ')' characters and a printing function > print :: Parens -> String > print Empty = "" > print (Wrap m) = "(" ++ print m ++ ")" > print (Append x y) = print x ++ print y So the idea is that I would like to write parse :: String -> Maybe Parens, such that if it gives Nothing then the String was malformed, if it gives Just x then the string should be equal to print x. I think I can write such a function in a few different ways, but I don't know how to prove this code works, could anybody show me how? Thank you for any replies. -- View this message in context: http://www.nabble.com/Parsing-with-Proof-tp22814576p22814576.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 3

Re: Definition of "tail recursive" wrt Folds
by Ben Franksen 01 Apr '09

01 Apr '09

Mark Spezzano wrote: > Just looking at the definitions for foldr and foldl I see that foldl is > (apparently) tail recursive while foldr is not. > > Why? > > Is it because foldl defers calling itself until last whereas foldr > evaluates itself as it runs? > > What, strictly speaking, is the definition of ”tail recursive” as opposed > to just “recursive”? An application of some function f inside another function g is in 'tail position' (or a 'tail call') if the result of applying f is the result of g. Operationally speaking, calling f is the very last thing g does. Tail calls can be optimized by a compiler (or interpreter) so that the call does not use additional stack; that is, the call can be replaced by a jump. A function is called ”tail recursive” (as opposed to just “recursive”) if the recursive call to itself is in tail position. If the compiler performs tail call optimization, tail recursive functions can work with constant stack space, similar to a (imperative) loop. Looking at a definition of foldl, e.g. foldl f z0 xs0 = lgo z0 xs0 where lgo z [] = z lgo z (x:xs) = lgo (f z x) xs you see that lgo calls itself in tail position, thus is tail recursive. In contrast, foldr can be defined as foldr k z xs = go xs where go [] = z go (y:ys) = y `k` go ys where you see that the result of go is not the recursive call to go. Instead, the result is y `k` go ys . Thus, foldr is not tail recursive. So, if you are saying that "foldl defers calling itself until last whereas foldr evaluates itself as it runs" then you got the right idea, I think. The point is that foldr still needs to do something (namely to apply (y `k`)) to the result of applying itself. It needs to remember to do so, and thus the stack grows linearly with the size of the list. Cheers Ben

2 2

ANN: cmonad 0.1.1
by Lennart Augustsson 01 Apr '09

01 Apr '09

I've uploaded my CMonad package to Hackage. It allows you to write Haskell code in a C style. Unfortunately, GHC lacks certain optimizations to make efficient code when using CMonad, so instead of C speed you get low speed. Example: Computing some Fibonacci numbers: fib = do { a <- arrayU[40]; i <- auto 0; a[0] =: 1; a[1] =: 1; for (i =: 2, (i :: EIO Int) < 40, i += 1) $ do { a[i] =: a[i-1] + a[i-2]; }; retrn (a[39]); } Example: Copying stdin to stdout: cat = do { c <- auto 0; while ((c =: getchar()) >= 0) $ do { putchar(c); }; return (); } -- Lennart

16 22

[SoC] XML Schema Implementation
by Vlad Dogaru 01 Apr '09

01 Apr '09

Hello everyone, I am writing to judge interest in a Summer of Code proposition: an XML Schema[1] implementation, described as a possbile application here[2]. As both a tool and an inspiration, I intend to use HaXML[3]. More specifically, I would be interested in the degree the Haskell community uses XML Schema, and if you were tempted to use it if we had an implementation. To further expand the question, how useful do you consider each of these components: * a validator * a pretty-printer * a translator from XML Schema to Haskell, similar to DtdToHaskell[4] For the latter item, some runtime checking will definitely be required: restrictions such as value ranges for integers or minimum and maximum occurences of an element cannot, to my knowledge, be enforced through type definitions. Finally, I kindly ask anyone with relevant experience to point out other possible pitfalls. Vlad Dogaru [1] http://www.w3schools.com/Schema/ [2] http://hackage.haskell.org/trac/summer-of-code/ticket/1120 [3] http://www.cs.york.ac.uk/fp/HaXml/ [4] http://www.cs.york.ac.uk/fp/HaXml/Xml2Haskell.html

6 6