July 2007 - Haskell-Cafe

Class Interfaces in OOHaskell?
by Scott West 06 Jul '07

06 Jul '07

Hello all, Looking at the OOHaskell black (grey?) magic, and wondering if there would be an interesting way to construct class interfaces using the OOHaskell paradigm? I'm trying to do it as so (assume relevant types/proxies declared): type FigureInter = Record ( Draw :=: IO () :*: HNil ) figure self = do return emptyRecord where _ = narrow self :: FigureInter abstrFigure self = do super <- figure self visible <- newIORef True returnIO $ setVisible .=. (\b -> writeIORef visible b) .*. isVisible .=. readIORef visible .*. draw .=. return () .<. super but ghci complains (you know how it likes to complain), with Couldn't match expected type `Record t2' against inferred type `F (Proxy Draw) (m ())' In the second argument of `(.*.)', namely `draw .=. (return ())' In the second argument of `(.*.)', namely `(isVisible .=. (readIORef visible)) .*. (draw .=. (return ()))' In the first argument of `(.<.)', namely `(setVisible .=. (\ b -> writeIORef visible b)) .*. ((isVisible .=. (readIORef visible)) .*. (draw .=. (return ())))' Anyone have any tips they care to share? :) Scott

2 2

Re: Combinators for Bi-Directional Tree Transformations: A Linguistic Approach to the View Update Problem" in Haskell
by Benjamin Pierce 06 Jul '07

06 Jul '07

Hi Titto, I'm not aware of any Haskell implementations of these bi-directional combinators, but the core definitions are not very big -- someone looking at the ML code should have no trouble recreating them in Haskell. The main issue to take care of, beyond the mathematical description in the paper, is doing enough memoization of intermediate structures. (Implementing a full-blown programming language based on these combinators is a more serious project, but even there the amount of code is not that large -- it's the design that takes time, and that you can just steal. :-) Regards, - Benjamin P.S. Please cc me directly on any responses -- I don't read the HaskellCafe list regularly...

2 1

Nix for Hackage/Cabal
by apfelmus 06 Jul '07

06 Jul '07

Hello, http://nix.cs.uu.nl/index.html "Nix is a purely functional package manager. This means that it treats packages like values in purely functional programming languages such as Haskell - they are built by functions that don't have side-effects, and they never change after they have been built." To me, it sounds like the ideal solution to package/make/build management in general and Cabal/Hackage/Cabal-install in particular. After all, compilation is just a _pure_ function compile :: Source -> Dependencies -> Object So, the suggestion is to use Nix for Hackage/Cabal. This way, we get package installation/deinstallation for free. I didn't look into it, but it seems that the package description language can express most content from .cabal files and I guess that it even eliminates the need for most of Cabal's functionality like finding compilers and such. The only drawback is that Nix uses a home-brew functional language for package descriptions. Of course, it would be ideal to have a Haskell DSL for that :) Regards, apfelmus

7 7

Abstraction leak
by Andrew Coppin 06 Jul '07

06 Jul '07

...and again today I found myself trying to do something that would be very easy in an imperative language, but I cannot think of a single good way of doing it in Haskell. Hopfully somebody can give me some hints. I'm writing a whole bunch of data compression programs. In particular, one of them was a Huffman encoder. The encoder scans the input file, computes symbol frequencies, and builds a canonical Huffman table, which it then dumps to file. The actual compressed data goes after that. The encoder consists of two functions. One takes the Huffman table and serializes it. The other does the actual encoding. The (++) operator joins the two together before going to file. Getting the data back is mildly more tricky. There's a decoder function that takes the complete data stream, parses out the Huffman table, and returns a pair containing the Huffman table and the remaining data. Then a second decoder function actually does the Huffman decoding on this data. So far, it's all pretty easy. The size of the Huffman table determins how many bytes the decoder needs to read, so it's easy to figure out where the table ends. And then I had a brainwave. I altered the encoder so that the output from the Huffman table serialize function codes through a simple RLE encoder before going to file. Then a went and altered the decoder to... uh... oops. Now I have a problem. It's easy enough to pass the entire data stream through an RLE decoder and feed that to the Huffman table deserialize function, and it will give be back the table. But I now have *no clue* where the table ends in the original stream! If this was Java, you would write all these compression and decompression stages as stream wrappers. So you wrap the raw input stream with an RLE decoder, have the function read the Huffman table, and then take off the RLE decoder and process the rest of the stream. However, in Haskell, the reading and deserializing of the Huffman table doesn't so anything detectable to the original data stream, so you can't tell how much of it the RLE decoder actually processed. Um... help! (What I did in the end was to write the size of the RLE encoded Huffman table to the file and read it back in the decoder. But this shouldn't actually be necessary...)

21 62

update on SoC projects?
by brad clawsie 06 Jul '07

06 Jul '07

does anyone have any interesting update info on the haskell SoC (summer of code) projects? in particular i am intersted in the haskell bindings to libcurl

4 3

Branches of a binary tree
by Kyle L Bittinger 06 Jul '07

06 Jul '07

I am writing some code to find peaks in molecular spectra. I represent a spectrum as a list of numbers (intensities) and build a binary search tree of the positions in the list (x-values) sorted by intensity. Peaks in the spectrum appear as branches of the tree. My task is to return branches of a binary tree that contain no other branches larger than some size. I wrote this function to test whether a tree can be classified as a peak. I suspect it's very inefficient, and it doesn't seem idiomatic to me either. I'm looking for suggestions to improve it: -- |Returns True if the tree can be classified as a peak. Peaks are -- qualified by not having any two branches with a size greater than n. isPeak :: Int -> Tree a -> Bool isPeak _ Tip = True isPeak n (Node _ l r) | (ltn l) && (ltn r) = True | (ltn l) && (gtn r) = isPeak n r | (gtn l) && (ltn r) = isPeak n l | (gtn l) && (gtn r) = False | otherwise = error "isPeak: no matching condition in guard" where gtn = (>=n) . size ltn = (<n) . size The "things to avoid" section of the haskell wiki suggests using an "atLeast" function for testing the length of lists. I don't know how to write this for trees, but I could do something like: gtn = atLeast n . flatten ltn = not . gtn The rest of my module is below. Most of it is standard binary tree stuff. Any suggestions would be much appreciated! --Kyle data Tree a = Tip | Node a (Tree a) (Tree a) deriving Show insert :: Ord a => Tree a -> a -> Tree a insert Tip x = Node x Tip Tip insert (Node y l r) x | x <= y = Node y (insert l x) r | otherwise = Node y l (insert r x) growTree :: Ord a => [a] -> Tree a growTree = foldl insert Tip size :: Tree a -> Int size Tip = 0 size (Node x l r) = 1 + (size l) + (size r) flatten :: Tree a -> [a] flatten Tip = [] flatten (Node x l r) = flatten l ++ [x] ++ flatten r atLeast :: Int -> [a] -> Bool atLeast 0 _ = True atLeast _ [] = False atLeast n (_:ys) = atLeast (n-1) ys peaks :: Int -> Tree a -> [[a]] peaks _ Tip = [] peaks n t@(Node _ l r) | isPeak n t = [flatten t] | otherwise = peaks n l ++ peaks n r -- Stolen from <http://haskell.org/haskellwiki/Blow_your_mind> sortIndicies ys = map fst $ L.sortBy (comparing snd) $ zip [0..] ys where comparing f x y = compare (f x) (f y)

2 1

Problem using ap -- No instance for (Monad ((->) [[a]]))
by Jim Burton 06 Jul '07

06 Jul '07

If I try a function to make a point-free version of the function in this fold -- foldr (\x ys -> ys ++ map (x:) ys) [[]] :pl gives me GOA Control.Monad> :pl (\x ys -> ys ++ map (x:) ys) ap (++) . map . (:) GOA Control.Monad> :t ap (++) . map . (:) ap (++) . map . (:) :: (Monad ((->) [[a]])) => a -> [[a]] -> [[a]] but this is what happens if I try to use it: GOA Control.Monad> let ps = foldr (ap (++) . map . (:)) [[]] <interactive>:1:16: No instance for (Monad ((->) [[a]])) arising from use of `ap' at <interactive>:1:16-22 Possible fix: add an instance declaration for (Monad ((->) [[a]])) In the first argument of `(.)', namely `ap (++)' In the first argument of `foldr', namely `((ap (++)) . (map . (:)))' In the expression: foldr ((ap (++)) . (map . (:))) [[]] (0.00 secs, 0 bytes) What gives? -- View this message in context: http://www.nabble.com/Problem-using-ap----No-instance-for-%28Monad-%28%28-%… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 1

reimplementing break (incorrectly) "quickcheck p list" gives me feedback that it breaks on list, but not what predicate test caused the breakage
by Thomas Hartman 06 Jul '07

06 Jul '07

I am a total quickcheck noob. Is there a way to find out what predicate test "<function>" is, below? Also, is there a way I can ask quickcheck to test lists of various built in types, not just Int? *********** Falsifiable, after 4 tests: <function> [1] *Recursion> testMyBreak Falsifiable, after 1 tests: <function> [-1,1,2] *Recursion> testMyBreak = quickCheck $ \p l -> myBreak p (l :: [Int]) == break p l myBreak t xs = let f t next rest = if t next then ([], snd rest) else (next : fst rest, snd rest) in foldr ( f t ) ([],[]) xs --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

3 2

"Combinators for Bi-Directional Tree Transformations: A Linguistic Approach to the View Update Problem" in Haskell
by Pasqualino 'Titto' Assini 06 Jul '07

06 Jul '07

Hi, I wondered if anyone had written an Haskell implementation of the combinators described in: "Combinators for Bi-Directional Tree Transformations: A Linguistic Approach to the View Update Problem" (see the Papers section of http://www.seas.upenn.edu/~harmony/) Harmony's source is in O'Caml so I guess that a translation in Haskell should not be to hard. More in general, is there any work in Haskell on "updateable views" of generic data structures? Thanks, titto

1 0

folds with escapes
by Michael Vanier 05 Jul '07

05 Jul '07

I'm sure this has been done a hundred times before, but a simple generalization of foldl just occurred to me and I wonder if there's anything like it in the standard libraries (I couldn't find anything). Basically, I was trying to define the "any" function in terms of a fold, and my first try was this: > any :: (a -> Bool) -> [a] -> Bool > any p = foldl (\b x -> b || p x) False This is inefficient, because if (p x) is ever True the rest of the list is scanned unnecessarily. So I wrote a more general foldl with an "escape" predicate which terminates the evaluation, along with a function which tells what to return in that case (given an argument of the running total 'z'): > foldle :: (b -> Bool) -> (a -> a) -> (a -> b -> a) -> a -> [b] -> a > foldle _ _ _ z [] = z > foldle p h f z (x:xs) = if p x then h z else foldle p h f (f z x) xs Using this function, "foldl" is: > foldl' = foldle (const False) id and "any" is just: > any p = foldle p (const True) const False I also thought of an even more general fold: > foldle' :: (b -> Bool) -> (a -> b -> [b] -> a) -> (a -> b -> a) -> a -> [b] -> a > foldle' _ _ _ z [] = z > foldle' p h f z (x:xs) = if p x then h z x xs else foldle' p h f (f z x) xs Using this definition, you can write "dropWhile" as: > dropWhile :: (a -> Bool) -> [a] -> [a] > dropWhile p = foldle' (not . p) (\_ x xs -> x:xs) const [] Again, I'm sure this has been done before (and no doubt better); I'd appreciate any pointers to previous work along these lines. Mike

8 9