May 2011 - Haskell-Cafe

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

"In several chapters there is a penetrating conceptual analysis of the matter at hand, on which a superstructure of code is erected."
by KC 21 May '11

21 May '11

Interesting comment on the book "The Fun of Programming" in JOOP. "In several chapters there is a penetrating conceptual analysis of the matter at hand, on which a superstructure of code is erected." -- -- Regards, KC

1 0

Is there a place where we can have a discussion on the merits of various GUI's & various graphics? And then vote?
by KC 20 May '11

20 May '11

:) -- -- Regards, KC

1 1

。就qhyrdvefhvfgyvvr，fhfxuhxxyvvhvvvvvghvvvvvrvvvvvvvvevx。
by andrew 20 May '11

20 May '11

466

1 0

Reverse Show instance
by Andrew Coppin 20 May '11

20 May '11

Cannot deduce (Show x) from context (Show (x, y)). Cannot deduce (Show y) from context (Show (x, y)). Um... seriously? From Prelude, we have Show x, Show y => Show (x, y) So clearly it works in the forward direction. But apparently not in the reverse direction. Is this a bug or a feature? (I.e., is there some obscure possibility I haven't thought of which means that doing the reverse inference would be incorrect?)

5 5