- Haskell-Cafe - Haskell.org

Could someone give me a small code review
by Aaron Gray 01 Jan '11

01 Jan '11

I have attached a tiny parser and lexer. This is really key to getting the lexing correct. The only thing I could not get neatly was to disallow hyphens at the end of identifiers, so have left it off until a good solution arrives. I plan to move over to monads next. Any comments welcome, Aaron

2 2

Haskell Weekly News: Issue 163 - Year End Issue
by Daniel Santa Cruz 31 Dec '10

31 Dec '10

Welcome to issue 163 of the HWN, a newsletter covering developments in the [1]Haskell community. This release of the newsletter contains some summary data for the year 2010. Thanks to everyone involved for making this such a wonderful community! Big cheers to Miran Lipovaa, who got multiple top Reddit stories this year for his work on Learn You a Haskell! Also kudos to Don Stewart, Norman Ramsey, camccann, sepp2k, and KennyTM for taking the time to answer so many questions in StackOverflow. The folks at #haskell never cease to amaze with their friendliness and their helpfulness as well. What did Reddit and StackOverflow think was hot this year? Top Reddit Stories this Year * Galois releases the Haskell Lightweight Virtual Machine (HaLVM): From (galois.com) scored 103 with 26 comments. Read on [2]reddit or the [3]original post. * Try Haskell!: From (self.haskell), scored 105 with 29 comments. Read on [4]reddit or the [5]original post. * GHC 7.0.1 released!: From (haskell.org) scored 100 with 31 comments. Read on [6]reddit or the [7]original post. * Learn You a Haskell: Zippers: From (learnyouahaskell.com) scored 93 with 44 comments. Read on [8]reddit or the [9]original post. * The new LLVM backend to GHC is ready to merge in!: From (haskell.org) scored 89 with 27 comments. Read on [10]reddit or the [11]original post. * Haskell vs. Erlang for bittorent clients: laziness, dynamic typing ..: From (jlouisramblings.blogspot.com) scored 88 with 8 comments. Read on [12]reddit or the [13]original post. * There are more than 4000 people in the Haskell Reddit. Tell us what you're using Haskell for! Work and/or play? What would most help you get the job done?: From (self.haskell), scored 84 with 171 comments. Read on [14]reddit or the [15]original post. * Smoking fast Haskell code using GHC's new LLVM codegen: From (donsbot.wordpress.com) scored 83 with 2 comments. Read on [16]reddit or the [17]original post. * Learn You a Haskell for Great Good! The Book!: From (amazon.com) scored 79 with 29 comments. Read on [18]reddit or the [19]original post. * LYAH: Intro to Monads: From (learnyouahaskell.com) scored 78 with 49 comments. Read on [20]reddit or the [21]original post. Top StackOverflow Answers this Year * [22]Large-scale design in Haskell? | votes: 1 I talk a bit about this in Engineering Large Projects in Haskell and in the Design and Implementation of XMonad. Engineering in the large is about managing complexity. The primary code structuring mechanisms in Haskell for managing complexity are : The type system Use the type system to enforce abstractions, simplifying interactions. Enforce key ... * [23]Curious about the HashTable problem | votes: 1 The problem was that the garbage collector is required to traverse mutable arrays of pointers ("boxed arrays") looking for pointers to data that might be ready to deallocate. Boxed, mutable arrays are the main mechanism for implementing a hashtable, so that particular structure showed up the GC traversal issue. This is common to many languages. The symptom ... * [24]Why are side-effects modeled as monads in Haskell? | votes: 1 Suppose a function has side effects. If we take all the effects it produce as the input and output parameters, then the function is pure to the outside world. So for an impure function f' :: Int -> Int we add the RealWorld to the consideration f :: Int -> RealWorld -> (Int, RealWorld) -- input some states of the whole world, -- modify the ... * [25]Haskell - I am too old for this Švotes: 1 (f . g) x = f (g x) This is true. You concluded from that that (f . g) x y = f (g x y) must also be true, but that is not the case. In fact, the following is true: (f . g) x y = f (g x) y which is not the same. Why is this true? Well (f . g) x y is the same as ((f . g) x) y and since we know that (f . g) x = f (g x) we can reduce that to (f (g x)) ... * [26]Haskell: How is <*> pronounced? | votes: 1 Sorry, I don't really know my math, so I'm curious how to pronounce the functions in the Applicative typeclass Knowing your math, or not, is largely irrelevant here, I think. As you're probably aware, Haskell borrows a few bits of terminology from various fields of abstract math, most notably Category Theory, from whence we get functors and monads. The ... * [27]Haskell Weird Kinds | votes: 1 These are GHC-specific extensions of the Haskell kind system. The Haskell 98 report specifies only a simple kind system: ... type expressions are classified into different kinds, which take one of two possible forms: The symbol * represents the kind of all nullary type constructors. If k1 and k2 are kinds, then k1->k2 is the kind of types ... * [28]Is Haskell really a purely functional language considering unsafePerformIO? | votes: 1 The Languages We Call Haskell unsafePerformIO is part of the Foreign Function Interface specification, not core Haskell 98 specification. It can be used to do local side effects that don't escape some scope, in order to expose a purely functional interface. That is, we use it to hide effects when the type checker can't do it for us (unlike the ST monad, ... * [29]What language to learn after Haskell? | votes: 1 I would like to broaden my knowledge of programming. (...) I thought I would pose the question here, along with several stipulations about the type of language I am looking for. Some are subjective, some are intended to ease the transition from Haskell. Strong type system. (...) It also makes informally reasoning about the correctness of my program ... * [30]Why is writing a compiler in a functional language easier? | votes: 1 Often times a compiler works a lot with trees. The source code is parsed into a syntax tree. That tree might then be transformed into another tree with type annotations to perform type checking. Now you might convert that tree into a tree only containing core language elements (converting syntactic sugar-like notations into an unsugared form). Now you might ... * [31]GHC's RTS options for garbage collection | votes: 1 Generally speaking, garbage collection is a space/time tradeoff. Give the GC more space, and it will take less time. There are (many) other factors in play, cache in particular, but the space/time tradeoff is the most important one. The tradeoff works like this: the program allocates memory until it reaches some limit (decided by the GC's automatic tuning ... About the Haskell Weekly News At this point in time, the HWN has been a bit sporadic. I'm hoping that 2011 will see a much more regular schedule for this channel. I'd like to thank everyone who pitched in and sent stories/comments/quotes. If you have any ideas of how to improve this letter, please don't hesitate to contact me at dstcruz(a)gmail.com. The source code that I use to cullate this newsletter will be made available shortly in github. Here is to wishing you a great 2011! Until next time, Daniel Santa Cruz References 1. http://haskell.org/ 2. http://www.reddit.com/r/haskell/comments/ee4ve/galois_releases_the_haskell_… 3. http://www.galois.com/blog/2010/11/30/galois-releases-the-haskell-lightweig… 4. http://www.reddit.com/r/haskell/comments/b58rk/try_haskell/ 5. file://localhost/r/haskell/comments/b58rk/try_haskell/ 6. http://www.reddit.com/r/haskell/comments/e6o0y/ghc_701_released/ 7. http://haskell.org/ghc/download_ghc_7_0_1.html 8. http://www.reddit.com/r/haskell/comments/e0qqz/learn_you_a_haskell_zippers/ 9. http://learnyouahaskell.com/zippers 10. http://www.reddit.com/r/haskell/comments/b3tby/the_new_llvm_backend_to_ghc_… 11. http://www.haskell.org/pipermail/cvs-ghc/2010-February/052606.html 12. http://www.reddit.com/r/haskell/comments/bwrhz/haskell_vs_erlang_for_bittor… 13. http://jlouisramblings.blogspot.com/2010/04/haskell-vs-erlang-for-bittorent… 14. http://www.reddit.com/r/haskell/comments/bhygx/there_are_more_than_4000_peo… 15. file://localhost/r/haskell/comments/bhygx/there_are_more_than_4000_people_in_the_haskell/ 16. http://www.reddit.com/r/haskell/comments/b4tel/smoking_fast_haskell_code_us… 17. http://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghc… 18. http://www.reddit.com/r/haskell/comments/dook4/learn_you_a_haskell_for_grea… 19. http://www.amazon.com/Learn-You-Haskell-Great-Good/dp/1593272839/ 20. http://www.reddit.com/r/haskell/comments/d51ao/lyah_intro_to_monads/ 21. http://learnyouahaskell.com/monads 22. http://stackoverflow.com/questions/3077866/large-scale-design-in-haskell/30… 23. http://stackoverflow.com/questions/3058529/curious-about-the-hashtable-prob… 24. http://stackoverflow.com/questions/2488646/why-are-side-effects-modeled-as-… 25. http://stackoverflow.com/questions/3884121/haskell-i-am-too-old-for-this/38… 26. http://stackoverflow.com/questions/3242361/haskell-how-is-pronounced/324285… 27. http://stackoverflow.com/questions/3034264/haskell-weird-kinds/3034295#3034… 28. http://stackoverflow.com/questions/3124591/is-haskell-really-a-purely-funct… 29. http://stackoverflow.com/questions/3770774/what-language-to-learn-after-has… 30. http://stackoverflow.com/questions/2906064/why-is-writing-a-compiler-in-a-f… 31. http://stackoverflow.com/questions/3171922/ghcs-rts-options-for-garbage-col…

1 0

Deep concatenation [Was: Incorrectly inferring type [t]]
by oleg＠okmij.org 31 Dec '10

31 Dec '10

William Murphy wrote: > I've spent a lot of time trying to write a version of concat, which > concatenates lists of any "depth": It is a little bit more involved, but quite possible. The code is not much longer than the one you wrote (essentially, three lines: one class and two instance declarations). Here is the complete code: {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} {-# LANGUAGE TypeFamilies, FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE OverlappingInstances #-} module DeepFlat where class DeepFlat a b | a -> b where dflat :: [a] -> [b] -- If we flatten a list of lists instance DeepFlat a b => DeepFlat [a] b where dflat = concatMap dflat -- If we are given a list of non-lists instance a ~ b => DeepFlat a b where dflat = id test1 = dflat "abracadabra" -- "abracadabra" test2 = dflat ["abra","cadabra"] test3 = dflat [["ab","ra"],["cad","abra"]] test4 = dflat [[["a","b"],["ra"]],[["cad","abra"]]]

2 1

Many broken links
by Henk-Jan van Tuyl 31 Dec '10

31 Dec '10

L.S., I find, quite often, links to haskell.org/xxx pages that have disappeared; isn't it possible to just copy all of these pages, to the original location, before the old server disappears? I used the W3C link checker[0] to check links from the GUI libraries page[1]; the following pages were reported missing: - http://haskell.org/FranTk - http://www.haskell.org/fruit/ - http://haskell.org/ObjectIO - http://haskell.org/graphics/ Other (sets of) pages that are missing: - http://haskell.org/gtk2hs/ - http://haskell.org/hdirect/ - http://www.haskell.org/~simonmar/ - http://www.haskell.org/sitewiki/ - http://www.haskell.org/all_about_monads - http://darcs.haskell.org/hfuse/ - http://darcs.haskell.org/yaht - http://haskell.org/haskore/ - http://www.haskell.org/yampa/ - http://darcs.haskell.org/~lemmih/ and probably many more. I suppose some of the maintainers have left, but the pages might still have some value. Some pages might be copied to the HaskellWiki, if the author gives permission to do so. It would also be good, to know which of these pages are obsolete, so that the links to these pages can be removed. Regards, Henk-Jan van Tuyl [0] http://validator.w3.org/checklink/ [1] http://www.haskell.org/haskellwiki/Applications_and_libraries/GUI_libraries -- http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html --

1 0

Happy Parser problem
by Aaron Gray 31 Dec '10

31 Dec '10

I am trying to get a grammar where keywords are also valid identifiers. Been messing round with the following Happy grammar :- %token 'let' { TokenIdent "let" } 'in' { TokenIdent "in" } ident { TokenIdent $$ } int { TokenInt $$ } '=' { TokenEq } '+' { TokenPlus } '-' { TokenMinus } '*' { TokenTimes } '/' { TokenDiv } '(' { TokenOB } ')' { TokenCB } %% Exp : 'let' Var '=' Exp 'in' Exp { Let $2 $4 $6 } | Exp1 { Exp1 $1 } Exp1 : Exp1 '+' Term { Plus $1 $3 } | Exp1 '-' Term { Minus $1 $3 } | Term { Term $1 } Term : Term '*' Factor { Times $1 $3 } | Term '/' Factor { Div $1 $3 } | Factor { Factor $1 } Factor :: { Factor } : int { Int $1 } | ident { Var $1 } | '(' Exp ')' { Brack $2 } Var :: { Factor } : ident { Var $1 } | 'let' { Var "let" } Here 'Var' should be able to represent a 'let' identifier, as well as a keyword. Happy accepts the grammar but it does not parser the expected 'let let = x in let'. I have attached the full Happy grammar. I don't think this is an LR thing, but could be wrong. Many thanks in advance, Aaron

1 1

A question regarding cmdargs package
by Ben Franksen 31 Dec '10

31 Dec '10

How can I disable the standard arguments 'help' and 'version'? Cheers

9 16

Newbie Question
by Chionidis Ioannis 31 Dec '10

31 Dec '10

Hello everybody! I am quite new to haskell programming. I am trying to make a gui for a drumming project made in euterpea and I want to do something like this : > b <- button f [text := "Run!" , on command := (test mambo_orig)] "test mambo_orig" is executed from ghci but I want It to be able to execute each time the user presses the button. Hope I didn't mess it up in the explaination, Giannis Chionidis

2 1

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

31 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