- Haskell-Cafe - Haskell.org

Further installation adventures
by Jacek Generowicz 23 May '11

23 May '11

I'm trying to cabal install lambdabot. This depends on a squillion other libraries, which cabal tries to install, among which is readline, which fails to configure as follows. Configuring readline-1.0.1.0... checking for gcc... gcc checking for C compiler default output file name... a.out checking whether the C compiler works... yes checking whether we are cross compiling... no checking for suffix of executables... checking for suffix of object files... o checking whether we are using the GNU C compiler... yes checking whether gcc accepts -g... yes checking for gcc option to accept ISO C89... none needed checking for GNUreadline.framework... checking for readline... no checking for tputs in -lncurses... no checking for tputs in -ltermcap... no checking for tputs in -lcurses... no checking for rl_readline_version... no configure: error: readline not found, so this package cannot be built See `config.log' for more details. cabal: Error: some packages failed to install: readline-1.0.1.0 failed during the configure step. The exception was: ExitFailure 1 From which I conclude that it can't find the readline library. I have all sorts of flavours of readline on my system, so I'll need a bit more information about what exactly it's looking for. It tells me to look in config.log. I presume that this is the config log of the cabal package readline, which cabal automatically downloaded, unpacked ... and presumably automatically cleaned up at the end, because I can't find it anywhere. Where should I be looking for the relevant config.log?

2 2

The Lisp Curse
by Andrew Coppin 23 May '11

23 May '11

http://www.winestockwebdesign.com/Essays/Lisp_Curse.html Some of you might have seen this. Here's the short version: Lisp is so powerful that it discourages reuse. Why search for and reuse an existing implementation, when it's so trivially easy to reimplement exactly what you want yourself? The net result is a maze of incompatible libraries which each solve a different 80% of the same problem. To all the people who look at Hackage, see that there are 6 different libraries for processing Unicode text files, and claim that this is somehow a *good* thing, I offer the above essay as a counter-example.

27 37

blaze-builder and FlexibleInstances in code that aims to become part of the Haskell platform
by Simon Meier 23 May '11

23 May '11

Hello Haskell-Cafe, my main question is whether requiring FlexibleInstances is a problem for code that aims to become part of the Haskell platform. The following explanation gives the context for this question. As some of you may know the blaze-builder library is now used in quite a few places. That's nice, but it doesn't mean that blaze-builder is a finished solution to the problem of providing an API for high-performance buffered output (creation of chunked representations) of sequences of bytes. In fact, one of my current goals with this work is to polish it such that it can be integrated into the 'bytestring' library. This has the benefit that functions that create lazy bytestrings (e.g., pack, map, unfoldr, filter) can be implemented such that they create well-sized chunks even if the argument bytestring is hugely fragmented. Moreover, this integration also establishes a single builder type as the output representation. Therefore, other creators of bytestrings (e.g., 'text', 'base16-bytestring', 'zlib') can provide results of type Builder, which enables O(1) appends of their results and the preservation of well-sizedness of the created chunks. As part of this goal, I'm currently working on the first of the following three points that are paramount to achieving great encoding performance: 1. Ensure that individual Haskell values are encoded with minimal overhead. 2. Ensure that concatenation of sequences of bytes is efficient. 3. Ensure that the average chunk size is large. The core principle used to tackle (1) is avoiding intermediate data structures. The core abstraction used is the one of a Write (see [1] for the corresponding library.) data Write a = Write Int (a -> Ptr Word8 -> IO (Ptr Word8)) A value `Write bound io :: Write a` denotes an encoding scheme for values of type `a` that uses at most `bound` bytes space. Given a values `x :: a` and a pointer `po` to the next free byte `io x po` encodes `x` to memory starting from `po` and returns the pointer to the next free byte after the encoding of `x`. In most cases Writes are used as an abstract datatype. They serve as an interface between implementors of the low-level bit-twiddling required to efficiently implement encodings like UTF-8 or Base16 and the providers of efficient traversal functions through streams of Haskell values. Hence, typical users of Writes are functions like fromWrite :: Write a -> a -> Builder fromWriteList :: Write a -> [a] -> Builder fromWriteUnfoldr :: Write b -> (a -> Maybe (b, a)) -> a -> Builder mapWriteByteString :: Write Word8 -> S.ByteString -> Builder They consume the given datastructure efficiently and wrap the Writes in the bounds checking code to detect when a buffer is full and request a new one. There are many providers of Writes. Each bounded-length-encoding of a standard Haskell value is likely to have a corresponding Write. For example, encoding an Int32 as a big-endian, little-endian, and host-endian byte-sequence is currently achieved with the following three functions. writeInt32BE :: Write Int32 writeInt32LE :: Write Int32 writeInt32HE :: Write Int32 I would like to avoid naming all these encodings individually. Especially, as the situation becomes worse for more elaborate encodings like hexadecimal encodings. There, we encounter encodings like the utf8-encoding of the hexadecimal-encoding with lower-case letters of an Int32. writeInt32HexLowerUtf8 :: Write Int32 I really don't like that. Therefore, I'm thinking about the following solution based on type-classes. We introduce a single typeclass class Writable a where write :: Write a and use a bunch of newtypes to denote our encodings. newtype Ascii7 a = Ascii7 { unAscii7 :: a } newtype Utf8 a = Utf8 { unUtf8 :: a } newtype HexUpper a = HexUpper { unHexUpper :: a } newtype HexLower a = HexLower { unHexLower :: a } ... Assuming FlexibleInstnaces, we can write encodings like the above hex-encoding as instances instance Write (Utf8 (HexLower Int32)) where write = ... This composes rather nicely and allows the implementations to exploit special properties of the involved data. For example, if we also had a HTML escaping marker newtype Html a = Html { unHtml :: a } Then, the instance instance Write (Utf8 (HTML (HexLower Int32))) where write (Utf8 (HTML (HexLower i))) = write (Utf8 (HexLower i)) exploits that no HTML escaping is required for a hex-number. Assuming FlexibleContexts, the user can also build abbreviations for builders using fixed encodings. utf8 :: Writable (Utf8 a) => a -> Builder utf8 = fromWrite write . Utf8 Note that, on the Builder level, a probably better way would be to have an analogous 'ToBuilder' typeclass to abstract the various encodings. Part of these instances then reuse the corresponding instances from Writable. I think this type-class based interface to select the correct efficient implementation of an encoding is rather nice. However, I don't know if 'FlexibleInstances' and 'FlexibleContexts' are fine to use in code that aims to become part of the Haskell platform. Moreover, I might well overlook some drawbacks of this design. I'm looking forward to your feedback. best regards, Simon [1] https://github.com/meiersi/system-io-write

7 17

Handling a large database (of ngrams)
by Aleksandar Dimitrov 23 May '11

23 May '11

Hi Haskellers, I'm unaware of a "good method" or "default way" of handling large datasets to which I need non-sequential (i.e. random) access in Haskell. My use case is linguistic analysis of a ~30GB corpus — the most basic form of quantitative analysis here are ngram based HMMs, which aren't difficult to pull of in Haskell. However, I would need a *large* database of ngrams, possibly into the hundreds of gigabytes. Such a beast will obviously never fit into memory. Moreover, I'll need sort of random access both during training and testing/operation. My initial idea (that I'm currently following up on) is to use Haskell's Berkeley DB wrapper. In this case, I would just stuff all ngrams in one big table (with their counts in an associated column,) and let Berkeley DB do the heavy lifting. One simplifying assumption is, of course, using the flyweight pattern (i.e. having one table of unigrams (that would even fit into memory!) associated with indices, and then just reference the indices in the ngram table.) But this is only going to decrease the size of the db by some factor, not an order of magnitude. Tries come to mind, too. Not only for the unigram table (where they indeed do make a lot of sense,) but also for the ngram table, where they might or might not help. In this case, the cells of the trie would be word indices pointing to the unigram table. Is there a way to serialize tries over a finite (but possibly large) domain to disk and have a semi-speedy random access to them? I'm fully aware that I'll have to wait up to a couple of seconds per lookup, that's OK. I could hack together a primitive implementation of what I need here, but maybe there's something better out there already? Hackage didn't speak to me[1], and #haskell was busy discussing something else, so I hope -cafe can help me :-) Thanks for any hints and pointers! Aleks [1] There's the ngram package on Haskell, but that only queries Google. I actually want to build my own ngram database, because I'm training on a specific corpus, and will possibly have to adapt to different domains.

2 3

Is there an efficient way to generate Euler's totient function for [2, 3..n]?
by KC 22 May '11

22 May '11

Is there an efficient way to generate Euler's totient function for [2,3..n]? Or an arithmetical sequence? Or a geometric sequence? Or some generalized sequence? -- -- Regards, KC

4 5

ANNOUNCE: wl-pprint-text 1.0.0.0
by Ivan Lazar Miljenovic 22 May '11

22 May '11

And lo, the people of Haskell hath declared that the text [1] library was to be the One True Way of dealing with textual data (unless, of course, you're annoyed about it using UTF-16 instead of UTF-8). And yet there was much sadness in the land, for there was no pretty-printing library available to produce said Text values, meaning that it was difficult for supplicants to produce the formatting their form of praise required. A voice then spake: make ye a new pretty-printing library aimed specifically for Text values. But thou shall not use the API from pretty [2], as it is rather limited. Instead, the design of wl-pprint [3] looks Real Good! It has more combinators available, can neatly deal with wrapping lists, and also has support for producing output for both humans and the machines that serve us so well! Thus were mighty energies aimed at producing such a library. Many were the hour at which toil was spent on this task, but at long last the task was completed. Yet great evil (i.e. programmer laziness) befell the great task, and it lay hidden for many a moon. However, with much effort the project was recovered, and is now available for all! [4] Some changes were regrettably required to achieve this task. The most important of which was that it was discovered that wl-pprint may not be as perfect as all that, in that documents of no content were treated poorly. However, spects of the pretty package were able to redeem themselves by supplying the necessary functionality. However, the great task was able to extend upon that which was there before, by invoking the almighty powers of the Monad. TL;DR: wl-pprint-text is a pretty-printing package for lazy Text values based upon the API of wl-pprint. It however deals with the nil document better than wl-pprint does, and also has a version where all the comibnators are lifted into a Monad, primarily so that it can be used within a State Monad. [1]: http://hackage.haskell.org/package/text [2]: http://hackage.haskell.org/package/pretty [3]: http://hackage.haskell.org/package/wl-pprint [4]: http://hackage.haskell.org/package/wl-pprint-text -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

1 0

ScopedTypeVariables in let-bindings (not where-bindings!) and bug 4347
by Paolo G. Giarrusso 21 May '11

21 May '11

Hi all, I have some problem with ScopedTypeVariables, let and so on, at least in GHC 7. My aim is to be able to supply a polymorphic type signature in let bindings. Confusingly, I find no such example in the blog post about local let generalization [1]. I first met this problem when porting some test-code from Kiselyov, when refusing to convert its let- bindings into where-bindings (which, btw, can't be typed into GHCi). I've also added a comment to the bug report, but it's still quite possible that I'm missing something. == Summary == My starting point today: I wanted to test polymorphic recursion by entering this definition into GHCi: a :: a -> a a = a a This is accepted without extra language pragmas but only with the type signature, due to the use of polymorphic recursion for which type inference is undecidable. To type it into GHCi I need to supply a polymorphic type in a let- binding. However, it turns out that Prelude> let id2 :: Int -> Int = \x -> x works but there's no way whatsoever to make the following work: Prelude> let (id2 :: forall t. t -> t) = \x -> x because of bug 4347. But let's start from the beginning. == Walk-through, with various other complaints. == So let's try this: $ ghci -XScopedTypeVariables Prelude> let a :: forall b. b -> b = a a [...request of enabling -XRank2Types or -XRankNTypes, confusing or BUGGY because the type is rank-1 ...] Prelude> :set -XRank2Types Prelude> let a :: forall b. b -> b = a a <interactive>:1:31: Couldn't match expected type `forall b. b -> b' with actual type `b0 -> b0' In the first argument of `a', namely `a' In the expression: a a In a pattern binding: a :: forall b. b -> b = a a Uh? That's strange. Seems an instance of bug #4347, but the error message is not yet the same. To get that, let's make an easier example: id. Of course, it needs no type signature, but if one can't give to this an explicit signature, realistic examples are hopeless. So, at the GHCi 7.0.3 prompt, I can't type: Prelude> let id2 :: t -> t = \x -> x GHCi first suggests using -XScopedTypeVariables. Let's try that: Prelude> :set -XScopedTypeVariables Prelude> let (id2 :: Int -> Int) = \x -> x This monomorphic function is fine, but the original polymorphic one is not accepted, it complains that t is not in scope - fine, let's add forall: *Main> let (id :: forall t. t -> t) = \x -> x <interactive>:1:6: Illegal polymorphic or qualified type: forall t. t -> t Perhaps you intended to use -XRankNTypes or -XRank2Types In a pattern type signature: forall t. t -> t In the pattern: id :: forall t. t -> t In a pattern binding: (id :: forall t. t -> t) = \ x -> x This is already confusing for me - the intended type is rank-1. But let's listen to GHCi again: Prelude> :set -XRank2Types Now, the error message is really puzzling: Prelude> let (id2 :: forall t. t -> t) = \x -> x <interactive>:1:33: Couldn't match expected type `t0 -> t1' with actual type `forall t. t -> t' The lambda expression `\ x -> x' has one argument, but its type `forall t. t -> t' has none In the expression: \ x -> x In a pattern binding: (id2 :: forall t. t -> t) = \ x -> x What's up? The documentation never mention let, but it does mention type signatures for patterns [2], and in "let a = b in c", "a" is IIRC a considered a pattern. Still, the lack of examples with let is already confusing. id2 :: forall t. t -> t = \x -> x How does "forall t. t -> t" have no argument? At worst, it expects a type-argument, in its System F representation . The only implementation problem I see in this code is that unification must "see through" the forall. I've seen this behavior described [3, 4], but all the problematic examples have been fixed in some way. Here, I see no direct fix. Best regards Paolo G. Giarrusso [1] http://hackage.haskell.org/trac/ghc/blog/LetGeneralisationInGhc7 [2] http://www.haskell.org/ghc/docs/7.0.3/html/users_guide/other-type-extension… [3] http://stackoverflow.com/questions/5885479/weird-error-when-using-scoped-ty… [4] http://hackage.haskell.org/trac/ghc/ticket/4347

6 12

Can't access map value with key.
by michael rice 21 May '11

21 May '11

What am I doing wrong in the last line of main? If I comment out the last line of main, my program prints the map (mp) that is created. If I leave it in, the program fails. The last line should print the list ["I"]. Michael ================================================ import Control.Monad.Stateimport Data.Map type Prefix = (String,String)type GeneratorState = State ((Map Prefix [String]),Prefix,[String]) non_word = "\n" f key new old = new ++ old buildMap :: GeneratorState (Map Prefix [String])buildMap = do (mp,(pfx1,pfx2),words) <- get if (Prelude.null words) then {- No more words. Return final map (adding non_word for prefix). -} return (insertWithKey' f (pfx1,pfx2) [non_word] mp) else do {- Add word to map at prefix & continue. -} put (insertWithKey' f (pfx1,pfx2) [head words] mp, (pfx2,(head words)), tail words) buildMap {-*Main> execState buildMap (singleton ("\n","\n") [], ("\n","\n"), ["I","am","lost."])(fromList [(("\n","\n"),["I"]),(("\n","I"),["am"]),(("I","am"),["lost."])],("am","lost."),[])*Main> -} nwords = 1 main = do contents <- getContents let mp = execState buildMap (singleton (non_word,non_word) [], (non_word,non_word), words contents) putStrLn $ show mp putStrLn $ show (mp ! (non_word,non_word)) ============================================== [michael@hostname ~]$ ghc --make markov4.hs[1 of 1] Compiling Main ( markov4.hs, markov4.o )Linking markov4 ...[michael@hostname ~]$ echo "I am lost." | ./markov4(fromList [(("\n","\n"),["I"]),(("\n","I"),["am"]),(("I","am"),["lost."])],("am","lost."),[])[michael@hostname ~]$ ghc --make markov4.hs[1 of 1] Compiling Main ( markov4.hs, markov4.o ) markov4.hs:35:27: Couldn't match expected type `Map k a' against inferred type `(Map Prefix [String], Prefix, [String])' In the first argument of `(!)', namely `mp' In the first argument of `show', namely `(mp ! (non_word, non_word))' In the second argument of `($)', namely `show (mp ! (non_word, non_word))'[michael@hostname ~]$

2 4

ghc error when I use MissingH
by Siddharth Karandikar 21 May '11

21 May '11

I am following an article by John Goerzen - http://www.freesoftwaremagazine.com/articles/haskell# Here, the very first example uses MissingH library. As I have ghci 7.0.3 and haskell-platform installed, I quickly installed this library using cabal. But ghc fails to find it. Here are the errors that I get - siddharth@mars:~/myprogs/hs$ ghc --make -o mh1 mh1.hs -v Glasgow Haskell Compiler, Version 7.0.3, for Haskell 98, stage 2 booted by GHC version 6.12.1 Using binary package database: /home/siddharth/tools/ghc/ghc-7.0.3/lib/ghc-7.0.3/package.conf.d/package.cache Using binary package database: /home/siddharth/.ghc/i386-linux-7.0.3/package.conf.d/package.cache wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-6bf7b03ebc9c668817e4379b6796c0c2 wired-in package integer-gmp mapped to integer-gmp-0.2.0.3-91607778cf3ae8f3948a50062b4f8479 wired-in package base mapped to base-4.3.1.0-cf5fbbf5ccbd0475ad054efbb121340e wired-in package rts mapped to builtin_rts wired-in package template-haskell mapped to template-haskell-2.5.0.0-f0c8f015e470d561d64a578434331367 wired-in package dph-seq not found. wired-in package dph-par not found. Hsc static flags: -static *** Chasing dependencies: Chasing modules from: *mh1.hs mh1.hs:1:8: Could not find module `MissingH.List': locations searched: MissingH/List.hs MissingH/List.lhs *** Deleting temp files: Deleting: *** Deleting temp dirs: Deleting: Thanks, Siddharth

2 2

Extension for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell
by KC 21 May '11

21 May '11

Extension for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- module SelectionProblem where import Data.Array import Data.List ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- Question: is there a way to get the type signature as the following: -- smallest :: (Ord a) => Int -> [Array Int a] -> a ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- Works on 2 finite ordered disjoint sets represented as sorted arrays. smallest :: (Ord a) => Int -> (Array Int a, Array Int a) -> a smallest k (xa,ya) = search k (xa,ya) (0,m+1) (0,n+1) where (0,m) = bounds xa (0,n) = bounds ya -- Removed some of the "indexitis" at the cost of calling another function. search :: (Ord a) => Int -> (Array Int a, Array Int a) -> (Int,Int) -> (Int,Int) -> a search k (xa,ya) (lx,rx) (ly,ry) | lx == rx = ya ! (k+ly) | ly == ry = xa ! (k+lx) | otherwise = case (xa ! mx < ya ! my) of (True) -> smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) (False) -> smallest2h k (ya,xa) ((ly,my,ry),(lx,mx,rx)) where mx = (lx+rx) `div` 2 my = (ly+ry) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array and ya the second array by their middle elements. smallest2h :: (Ord a) => Int -> (Array Int a, Array Int a) -> ((Int,Int,Int),(Int,Int,Int)) -> a smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) = case (k<=mx-lx+my-ly) of (True) -> search k (xa,ya) (lx,rx) (ly,my) (False) -> search (k-(mx-lx)-1) (xa,ya) (mx+1,rx) (ly,ry) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- Works on 3 finite ordered disjoint sets represented as sorted arrays. smallest3 :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> a smallest3 k (xa,ya,za) = -- On each recursive call the order of the arrays can switch. search3 k (xa,ya,za) (0,bx+1) (0,by+1) (0,bz+1) where (0,bx) = bounds xa (0,by) = bounds ya (0,bz) = bounds za -- Removed some of the "indexitis" at the cost of calling another function. search3 :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> (Int,Int) -> (Int,Int) -> (Int,Int) -> a search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,rz) | lx == rx && ly == ry = za ! (k+lz) | ly == ry && lz == rz = xa ! (k+lx) | lx == rx && lz == rz = ya ! (k+ly) | lx == rx = search k (ya,za) (ly,ry) (lz,rz) | ly == ry = search k (xa,za) (lx,rx) (lz,rz) | lz == rz = search k (xa,ya) (lx,rx) (ly,ry) | otherwise = case (xa ! mx < ya ! my, xa ! mx < za ! mz, ya ! my < za ! mz) of (True, True, True) -> smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) -- a<b<c (True, True, False) -> smallest3h k (xa,za,ya) ((lx,mx,rx),(lz,mz,rz),(ly,my,ry)) -- a<c<b (False, True, True) -> smallest3h k (ya,xa,za) ((ly,my,ry),(lx,mx,rx),(lz,mz,rz)) -- b<a<c (False, False, True) -> smallest3h k (ya,za,xa) ((ly,my,ry),(lz,mz,rz),(lx,mx,rx)) -- b<c<a (True, False, False) -> smallest3h k (za,xa,ya) ((lz,mz,rz),(lx,mx,rx),(ly,my,ry)) -- c<a<b (False, False, False) -> smallest3h k (za,ya,xa) ((lz,mz,rz),(ly,my,ry),(lx,mx,rx)) -- c<b<a where mx = (lx+rx) `div` 2 my = (ly+ry) `div` 2 mz = (lz+rz) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array, ya the second array, and za the third array by their middle elements. smallest3h :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> ((Int,Int,Int),(Int,Int,Int),(Int,Int,Int)) -> a smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) = case (k<=mx-lx+my-ly+mz-lz) of (True) -> search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,mz) (False) -> search3 (k-(mx-lx)-1) (xa,ya,za) (mx+1,rx) (ly,ry) (lz,rz) -- -- Regards, KC

2 1