- Haskell-Cafe - Haskell.org

Thunks and GHC pessimisation
by oleg＠okmij.org 26 Feb '13

26 Feb '13

Tom Ellis wrote: > To avoid retaining a large lazy data structure in memory it is useful to > hide it behind a function call. Below, "many" is used twice. It is hidden > behind a function call so it can be garbage collected between uses. As you discovered, it is quite challenging to ``go against the grain'' and force recomputation. GHC is quite good at avoiding recomputation. This is a trade-off, of time vs space. For large search tree, it is space that is a premium, and laziness and similar strategies are exactly the wrong trade-off. The solution (which I've seen in some of the internal library code) is to confuse GHC with extra functions: http://okmij.org/ftp/Haskell/misc.html#memo-off So, eventually it is possible to force recomputation. But the solution leaves a poor taste -- fighting a compiler is never a good idea. So, this is a bug of sort -- not the bug of GHC, but of lazy evaluation. Lazy evaluation is not the best evaluation strategy. It is a trade-off, which suits a large class of problems and punishes another large class of problems.

2 1

Parser left recursion
by Martin Drautzburg 26 Feb '13

26 Feb '13

Hello all, this was previously asked on haskell-beginners, but only partially answered. As an exercise I am writing a parser roughly following the expamples in Graham Hutton's book. The language contains things like: data Exp = Lit Int -- literal integer | Plus Exp Exp My naive parser enters an infinite recursion, when I try to parse "1+2". I do understand why: "hmm, this expression could be a plus, but then it must start with an expression, lets check". and it tries to parse expression again and again considers Plus. Twan van Laarhoven told me that: > Left-recursion is always a problem for recursive-descend parsers. and suggested to do something like: > parseExp = do > lit <- parseLit > pluses <- many (parsePlusToken *> parseLit) > return (combinePlusesWithLit lit pluses) > > combinePlusesWithLit = foldr Plus -- or foldl This indeed does the trick, but only when the first token is a Lit (literal integer). I then added the possibility to optionally put things in parentheses. But then I cannot parse "(1+2)+3". The original code fails, because "(1+2)" is not a Lit and when I allow an expression as the first argument to "+" I get infinite recursion again. I am generally confused, that saying "a plus expression is an integer followed by many "plus somethings" is not what the language says. So this requires a lot of "paying attention" to get right. I'd much rather say "a plus expression is two expressions with a '+' in between". I do know for sure, that it is possible to parse "(1+2)+3" (ghci does it just fine). But I seem to be missing a trick. Can anyone shed some light on this? -- Martin

9 24

Status of GHC type-nats branch
by Takayuki Muranushi 26 Feb '13

26 Feb '13

Hi, everyone, In order to merge two type-level key-value pairs (More specifically, to use TypeNats branch of unittyped: https://bitbucket.org/xnyhps/haskell-unittyped/commits/all/tip/branch%28%22… ) I'd like to use overlapping type families and the type level Naturals at the same time. However, I couldn't build the type-nats branch of ghc, as I've been trying this week. I could build that in late 2012, so maybe this is due to updates in the git submodules. Do you reproduce this? Is there anyone else trying to build the type-nats branch? Any advice is helpful, including negative ones, if it's temporally broken or no more supported. And, I'm particularly glad if anyone has a x86-64 linux tarball of type-nats branch, and share it with me :) Best regards, -- Takayuki MURANUSHI The Hakubi Center for Advanced Research, Kyoto University http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

2 2

ifdef based on which OS you're on
by Andrew Cowie 26 Feb '13

26 Feb '13

I've got a piece of code that looks like this: baselineContextSSL :: IO SSLContext baselineContextSSL = do ctx <- SSL.context SSL.contextSetDefaultCiphers ctx #if defined __MACOSX__ SSL.contextSetVerificationMode ctx SSL.VerifyNone #elif defined __WIN32__ SSL.contextSetVerificationMode ctx SSL.VerifyNone #else SSL.contextSetCADirectory ctx "/etc/ssl/certs" SSL.contextSetVerificationMode ctx $ SSL.VerifyPeer True True Nothing #endif return ctx all very nice (this being necessary because apparently the non-free operating systems don't store their certs in a reliably discoverable place; bummer). That, however, is not the problem. After all, this sort of thing is what #ifdefs are for. The problem is needing to get an appropriate symbol based on what OS you're using defined. I naively assumed there would be __LINUX__ and __MACOSX__ and __WIN32__ defined by GHC because, well, that's just the sort of wishful thinking that powers the universe. So my question is: what's an appropriate Haskell mechanism for building code that is OS / arch / distro specific? It's not like I have autoconf running generating me a config.h I could #include, right? This feels simple and an appropriate use of CPP; even the symbol names look just about like what I would have expected; stackoverflow said so, must be true. Just need to get the right symbol defined at build time. Any suggestions? AfC Sydney

8 14

ANN: lazy-csv - the fastest and most space-efficient parser for CSV
by Malcolm Wallace 26 Feb '13

26 Feb '13

There are lots of Haskell CSV parsers out there. Most have poor error-reporting, and do not scale to large inputs. I am pleased to announce an industrial-strength library that is robust, fast, space-efficient, lazy, and scales to gigantic inputs with no loss of performance. http://code.haskell.org/lazy-csv/ Downloads from Hackage: http://hackage.haskell.org/package/lazy-csv This library has been in industrial use for several years now, but this is the first public release. No doubt the API is not as general as it could be, but it already serves many purposes very well. I'm happy to receive bug reports and suggestions for improvements. Regards, Malcolm

7 7

ANN: conduit-network-stream, A base layer for network protocols with Conduits
by Nils 25 Feb '13

25 Feb '13

Hello everyone, I just uploaded my "conduit-network-stream" package to hackage. It's a base layer for network protocols based on the "Conduit" package by Michael Snoyman which makes it possible to send multiple messages over a continuous network connection in a convenient way. I wrote more about it at: https://github.com/mcmaniac/conduit-network-stream/blob/master/README.md It is available on hackage and github: http://hackage.haskell.org/package/conduit-network-stream https://github.com/mcmaniac/conduit-network-stream Until the documentation on hackage is generated, I also host the haddock documentation at: http://hs.nils.cc/conduit-network-stream/index.html For any questions/problems/requests, please ask! - Nils

3 5

Thunks and GHC pessimisation
by Tom Ellis 25 Feb '13

25 Feb '13

To avoid retaining a large lazy data structure in memory it is useful to hide it behind a function call. Below, "many" is used twice. It is hidden behind a function call so it can be garbage collected between uses. That's good. When compiling with "-O" it seems that GHC 7.4.1 decides to keep it in memory anyway. That's bad. (I can't read core so I don't know exactly what's going on). Replacing one of the "many" in "twice" with "different_many" makes everything fine again. Is this considered a bug in GHC? Is it a known bug? It is incredibly concerning that GHC would perform this kind of pessimisation. Tom % cat thunkfail.hs {-# OPTIONS_GHC -fno-warn-unused-binds #-} import Data.List million :: Int million = 10 ^ (6 :: Int) many :: () -> [Int] many () = [1..million] different_many :: () -> [Int] different_many () = [1..million] twice :: (Int, Int) twice = (foldl' (+) 0 (many ()), foldl' (+) 0 (many ())) main :: IO () main = print twice % ghc -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs && ./thunkfail +RTS -M5M [1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o ) Linking thunkfail ... (1784293664,1784293664) % ghc -O -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs && ./thunkfail +RTS -M5M [1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o ) Linking thunkfail ... Heap exhausted; Current maximum heap size is 5242880 bytes (5 MB); use `+RTS -M<size>' to increase it.

3 5

Tournament knock out
by Xinyu LIU 25 Feb '13

25 Feb '13

Hi, Tournament knock out is explained in [1] by Knuth. The limitation is that it can only handle the sequence of the length 2^m for some integer m. When the champion element is removed, it was replaced with negative infinity. Typically negative infinity is represented by a predefined big negative number. Although heap sort solves all these limitation, I found tournament knock out itself can work out. Here is the Haskell code: data Infinite a = NegInf | Only a | Inf deriving (Eq, Show, Ord) only (Only x) = x data Tr a = Empty | Br (Tr a) a (Tr a) deriving Show key (Br _ k _ ) = k wrap x = Br Empty (Only x) Empty branch t1 t2 = Br t1 (min (key t1) (key t2)) t2 fromList :: (Ord a) => [a] -> Tr (Infinite a) fromList = build . (map wrap) where build [] = Empty build [t] = t build ts = build $ pair ts pair (t1:t2:ts) = (branch t1 t2):pair ts pair ts = ts pop (Br Empty _ Empty) = Br Empty Inf Empty pop (Br l k r) | k == key l = let l' = pop l in Br l' (min (key l') (key r)) r | k == key r = let r' = pop r in Br l (min (key l) (key r')) r' top = only . key tsort :: (Ord a) => [a] -> [a] tsort = sort' . fromList where sort' Empty = [] sort' (Br _ Inf _) = [] sort' t = (top t) : (sort' $ pop t) The detailed explanation can be found at: https://github.com/liuxinyu95/AlgoXY/blob/algoxy/preview/ssort-en.pdf?raw=t… [1]. Donald E. Knuth. The art of computer programming, Volume 3, sorting and searching. Larry, LIU Xinyu https://sites.google.com/site/algoxy/ https://github.com/liuxinyu95/AlgoXY

1 0

Re: [Haskell-cafe] Parser left recursion
by wren ng thornton 24 Feb '13

24 Feb '13

On 2/24/13 7:56 AM, Kim-Ee Yeoh wrote: > On Sun, Feb 24, 2013 at 7:47 PM, Roman Cheplyaka <roma(a)ro-che.info> wrote: > >> Or perhaps you meant that the production itself, when interpreted as a >> definition, is corecursive? > > I was merely thrown off by your mention of "well-founded" and the assertion > that you're left with a "strictly smaller" input. I don't see any of this. But the problem here really is an issue of well-foundedness rather than productivity. Consider the grammar, A ::= epsilon | A B B ::= ...whatever... In order to use this grammar as-is, when processing a string we must be able to magically determine how many times to recurse in order to get our epsilon. This is magic because the correct number of times to recurse is defined by the rest of the string--- which we haven't looked at! Proof theoretically speaking, this is the same as magically knowing when to use the inductive hypothesis vs when to bottom out at a base case. Using this grammar as-is, the recursive descent parser always decides to use the inductive hypothesis. Hence, infinite loop. It should be apparent that this isn't an issue with left-recursion (when reading the string from right to left), because on left-recursion we're always consuming some of the string, and therefore the input string is getting smaller on each recursive call, and therefore it is guaranteed that we will eventually run out of string, at which point we can backtrack as necessary. The problem with right-recursion is that we never know when to stop recurring. If we stop at some arbitrary point, well maybe the parse will end up failing when it could've succeeded if only we had recursed a bit further. But recursive descent doesn't allow the kind of backtracking that would be required to exhaust the search space for right-recursion. -- Live well, ~wren

1 0

presentation on Diffusion of Innovation mentioning several times Haskell
by Luc TAESCH 24 Feb '13

24 Feb '13

Just found an Interesting presentation mixing Diffusion of Innovation with Social Patterns, mentioning several times Haskell. Good introduction to a mix of techniques for whoever interested in Haskell proselytism, and go to market strategy, http://www.taesch.com/haskell/go-to-market/introduction-to-diffusion-of-inn…

1 0