June 2009 - Haskell-Cafe

Re: Question on rank-N polymorphism
by oleg＠okmij.org 09 Jun '09

09 Jun '09

Ryan Ingram discussed a question of writing > fs f g = (f fst, g snd) so that fs ($ (1, "2")) type checks. This is not that difficult: > {-# LANGUAGE RankNTypes, MultiParamTypeClasses -#} > {-# LANGUAGE FunctionalDependencies, FlexibleInstances #-} > > class Apply f x y | f x -> y where > apply :: f -> x -> y > > instance Apply (x->y) x y where > apply = ($) > > data Fst = Fst > data Snd = Snd > > instance Apply Fst (x,y) x where > apply _ = fst > > instance Apply Snd (x,y) y where > apply _ = snd The function in question: > fs3 f = (apply f Fst, apply f Snd) -- One of Wouter Swierstra's examples -- examples = (fs id, fs repeat, fs (\x -> [x]), fs ((,)id)) > data Id a = Id > instance Apply (Id a) Fst ((a,a) -> a) where > apply _ _ = fst > instance Apply (Id a) Snd ((a,a) -> a) where > apply _ _ = snd > ex1 = fs3 Id Now, Ryan's main example > newtype Pair a b = Pair (forall w. (((a,b) -> w) -> w)) > instance Apply (Pair a b) Fst a where > apply (Pair f) _ = f fst > instance Apply (Pair a b) Snd b where > apply (Pair f) _ = f snd > ex4 = fs3 (Pair ($ (1, "2"))) > -- (1,"2") Incidentally, a different variation of this example is discussed in http://okmij.org/ftp/Computation/extra-polymorphism.html Indeed, such a selection from a pair occurs quite often...

1 0

ANNOUNCE: StrictBench 0.1 - Benchmarking code through strict evaluation
by Niemeijer, R.A. 09 Jun '09

09 Jun '09

Hello everyone, In the last month or so, I've found myself using the following snippet a lot: import Control.Parallel.Strategies import Test.BenchPress bench 1 . print . rnf This snippet fully evaluates a value and prints how long it took to do so. I regularly use it to see where the bottlenecks lie in my algorithms. It has the minor annoyance, however, that it prints a lot of information (min, max, mean, median, percentiles) that is all identical, because I only run it once. The reason I only run it once is that I'm typically evaluating a pure value, which means that any subsequent attempts to benchmark the evaluation time will take no time at all, since it has already been evaluated. To solve this, I decided to write a small library to make this process easier and only print the time taken once. The result is StrictBench, which can be found at http://hackage.haskell.org/cgi-bin/hackage-scripts/package/StrictBench. A short example: import Test.StrictBench main = bench [1..10000000 :: Integer] This code would give 2890.625 ms as output. For the rest of the documentation I refer you to the Hackage page. Regards, Remco Niemeijer

6 6

Applying Data.Map
by michael rice 09 Jun '09

09 Jun '09

I wrote a Haskell solution for the Prolog problem stated below. I had written a function SQUISH before discovering that NUB does the same thing. While the solution works, I thought maybe I could apply some functions in the Data.Map module, and so wrote a second version of SERIALIZE, one no longer needing TRANSLATE. Using the Data.Map module is probably overkill for this particular problem, but wanted to familiarize myself with Map type. Suggestions welcome. Prolog code also included below for those interested. Michael =========== {- From "Prolog By Example", Coelho, Cotta, Problem 42, pg. 63 Verbal statement: Generate a list of serial numbers for the items of a given list, the members of which are to be numbered in alphabetical order. For example, the list [p,r,o,l,o,g] must generate [4,5,3,2,3,1] -} {- Prelude> :l serialize [1 of 1] Compiling Main ( serialize.hs, interpreted ) Ok, modules loaded: Main. *Main> serialize "prolog" [4,5,3,2,3,1] *Main> -} ===========Haskell code========== import Data.Char import Data.List import Data.Map (Map) import qualified Data.Map as Map {- translate :: [Char] -> [(Char,Int)] -> [Int] translate [] _ = [] translate (x:xs) m = (fromJust (lookup x m)) : (translate xs m ) -} {- serialize :: [Char] -> [Int] serialize s = let c = nub $ sort s n = [1..(length c)] in translate s (zip c n) -} serialize :: [Char] -> [Int] serialize s = let c = nub $ sort s n = [1..(length c)] m = Map.fromList $ zip c n in map (\c -> m Map.! c) s ============Prolog code============ serialize(L,R) :- pairlists(L,R,A),arrange(A,T), numbered(T,1,N). ? <- typo? pairlists([X|L],[Y|R],[pair(X,Y)|A]) :- pairlist(L,R,A). pairlists([],[],[]). arrange([X|L],tree(T1,X,T2)) :- partition(L,X,L1,L2), arrange(L1,T1), arrange(L2,T2). arrange([],_). partition([X|L],X,L1,L2) :- partition(L,X,L1,L2). partition([X|L],Y,[X|L1],L2) :- before(X,Y), partition(L,Y,L1,L2). partition([X|L],Y,L1,[X|L2]) :- before(Y,X), partition(L,Y,L1,L2). partition([],_,[],[]). before(pair(X1,Y1),pair(X2,Y2)) :- X1<X2. numbered(tree(T1,pair(X,N1),T2),N0,N) :- numbered(T1,N0,N1), N2 is N1+1, numbered(T2,N2,N). numbered(void,N,N). ============Prolog examples======== Execution: ?- serialize([p,r,o,l,o,g]). [4,5,3,2,3,1] ?- serialize ([i,n,t,.,a,r,t,i,f,i,c,i,a,l]). [5,7,9,1,2,8,9,5,4,5,3,5,2,6]

2 1

Slow documentation generation on Hackage
by Niemeijer, R.A. 08 Jun '09

08 Jun '09

Hello everyone. Last night I uploaded my first Hackage library with documentation (StrictBench). I learned that it takes somewhere between 2 and 8 hours for the link to the documentation to become active. This is confusing for first-time package authors (I went to #haskell to ask what I had forgotten) and annoying for everyone (Don Stewart submitted it to reddit shorly after I published it, which kind of wastes the time of everyone who checks it out before the documentation is up). Moreover, there seems to be no reason for it; on your own computer haddock takes just (milli)seconds. Hence I wanted to ask if this is a bug or if there is a good technical or social reason for it, and whether there is any way around it. Regards, Remco Niemeijer

7 8

Comonadic composition and the game "Doublets"
by Matthew 08 Jun '09

08 Jun '09

Today, I was working on coding a solver for the game "doublets". It's a word game where you transform the start word into the end word one letter at a time (and the intermediate states must also be valid words). For example, one solution to ("warm", "cold") is ["warm", "ward", "card", "cord", "cold"] So, one of my first goals was to write a function that would generate the possible words a given word could transition to. Here's a simple recursive implementation: transition :: [Char] -> [[Char]] transition [] = [] transition (c:cs) = map (c:) (transition cs) ++ map (:cs) ['a'..'z'] For some reason, I find this formulation to be strangely unsatisfying. It seems to me that this sort of computation -- i.e. modifying each element of a container (but only one at a time) -- should be expressible with some higher order function. In a nutshell, what I'm looking for would be a function, say "each" with this type. each :: (Container c) => (a -> a) -> c a -> c (c a) I'm not particularly sure what Class to substitute for "Container". Comonad seemed like a promising solution initially, and provides the basis for my current implementation of the "doublets" solver. The problem being that cobind (extend) takes a function of type (w a - > a) instead of (a -> a). I suspect that there may be a clever way to write "each" by using liftW in combination with .>> or something like that, but presently, I'm at a loss. Has anyone else encountered this sort of abstraction before. I'd love to hear your ideas about what Classes "each" should support, and how to implement it. Matt

3 3

Re: [Haskell-cafe] Incremental XML parsing with namespaces?
by John Millikin 08 Jun '09

08 Jun '09

On Mon, Jun 8, 2009 at 2:51 PM, wren ng thornton<wren(a)freegeek.org> wrote: > One issue you'll have to deal with is that since output is delivered > on-line, by the time a validity (or well-formedness) error can be recognized > by the parser it'll be "too late". Thus the rest of your code will need to > be able to back out any global changes they've done when an asynchronous > error shows up. > > I'm sure you already knew that, but it's worth highlighting. (I recently > wrote similar code, but in Java. Haven't had the chance/need to do any xml > hacking in Haskell yet.) > This is acceptable -- I've written a small Python application that performs incremental parsing on the data stream, and aborting on first detection of an error is fine.

1 0

com-1.2.3 - problems installing
by Günther Schmidt 08 Jun '09

08 Jun '09

Hi all, I'm trying to install com-1.2.3 on Win XP with ghc-6.10.3 I get this error message: Resolving dependencies... Configuring com-1.2.3... cabal: Missing dependencies on foreign libraries: * Missing header file: include/WideStringSrc.h * Missing C libraries: kernel32, user32, ole32, oleaut32, advapi32 This problem can usually be solved by installing the system packages that provide these libraries (you may need the "-dev" versions). If the libraries are already installed but in a non-standard location then you can use the flags --extra-include-dirs= and --extra-lib-dirs= to specify where they are. cabal: Error: some packages failed to install: com-1.2.3 failed during the configure step. The exception was: exit: ExitFailure 1

1 0

Re: [Haskell-cafe] Problem with Data.Map
by michael rice 08 Jun '09

08 Jun '09

Thanks, guys. Sounds like Lisp packages. Now I see the functionality of the A or B, etc.: Fewer keystrokes. Michael --- On Mon, 6/8/09, minh thu <noteed(a)gmail.com> wrote: From: minh thu <noteed(a)gmail.com> Subject: Re: [Haskell-cafe] Problem with Data.Map To: "michael rice" <nowgate(a)yahoo.com> Cc: "Jochem Berndsen" <jochem(a)functor.nl>, haskell-cafe(a)haskell.org Date: Monday, June 8, 2009, 1:00 PM Hi, > import Blurp bring every thing defined in the Blurp module in scope. So if blah is defined in blurp, > blah will work as expected. > import qualified Blurp as B does the same thing but everything defined in Blurp should be qualified (i.e. prefixed) with B. > B.blah will work, not > blah So your import statement is right but you should write Map.fromList instead of just fromList. The goal is to have multiple identical names from different modules and still be able to use them at the same time, but qualified, for instance lookup is defined in both Data.List and Data.Map. > import qualified Data.List as L > import qualified Data.Map as M > L.lookup > M.lookup The two last lines are unambiguous. Cheers, Thu 2009/6/8 michael rice <nowgate(a)yahoo.com>: > I don't understand your response. I copied the imports from Hoogles Data.Map > page. What should the imports be? > > Michael > > --- On Mon, 6/8/09, Jochem Berndsen <jochem(a)functor.nl> wrote: > > From: Jochem Berndsen <jochem(a)functor.nl> > Subject: Re: [Haskell-cafe] Problem with Data.Map > To: "michael rice" <nowgate(a)yahoo.com> > Cc: haskell-cafe(a)haskell.org > Date: Monday, June 8, 2009, 12:45 PM > > michael rice wrote: >> I'm trying to understand Map type for possible use in another problem I'm >> working on, but am stymied right off the bat. >> >> ==========Here's my source: >> >> import Data.Map (Map) >> import qualified Data.Map as Map >> >> *Main> fromList $ zip l1 l2 >> >> <interactive>:1:0: Not in scope: `fromList' > > You imported map "qualified as Map", that means that only 'Map.fromList' > and 'Data.Map.fromList' are in scope, and not 'fromList'. The reason one > normally does it like this is that a lot of function names clash with > the Prelude (on purpose). Normally one uses "qualified as M" or > "qualified as Map" to shorten the notation. > > HTH, > > -- > Jochem Berndsen | jochem(a)functor.nl > GPG: 0xE6FABFAB > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

1 0

Re: [Haskell-cafe] Problem with Data.Map
by michael rice 08 Jun '09

08 Jun '09

Gotcha. Thanks! Also wondering why I need two imports for one module. Michael --- On Mon, 6/8/09, Jochem Berndsen <jochem(a)functor.nl> wrote: From: Jochem Berndsen <jochem(a)functor.nl> Subject: Re: [Haskell-cafe] Problem with Data.Map To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Monday, June 8, 2009, 12:52 PM michael rice wrote: > I don't understand your response. I copied the imports from Hoogles Data.Map page. What should the imports be? > > Michael The imports are fine, but instead of 'fromList' you should use 'Map.fromList' or 'Data.Map.fromList'. Regards, -- Jochem Berndsen | jochem(a)functor.nl GPG: 0xE6FABFAB

2 1

Re: [Haskell-cafe] Problem with Data.Map
by michael rice 08 Jun '09

08 Jun '09

I don't understand your response. I copied the imports from Hoogles Data.Map page. What should the imports be? Michael --- On Mon, 6/8/09, Jochem Berndsen <jochem(a)functor.nl> wrote: From: Jochem Berndsen <jochem(a)functor.nl> Subject: Re: [Haskell-cafe] Problem with Data.Map To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Monday, June 8, 2009, 12:45 PM michael rice wrote: > I'm trying to understand Map type for possible use in another problem I'm working on, but am stymied right off the bat. > > ==========Here's my source: > > import Data.Map (Map) > import qualified Data.Map as Map > > *Main> fromList $ zip l1 l2 > > <interactive>:1:0: Not in scope: `fromList' You imported map "qualified as Map", that means that only 'Map.fromList' and 'Data.Map.fromList' are in scope, and not 'fromList'. The reason one normally does it like this is that a lot of function names clash with the Prelude (on purpose). Normally one uses "qualified as M" or "qualified as Map" to shorten the notation. HTH, -- Jochem Berndsen | jochem(a)functor.nl GPG: 0xE6FABFAB

3 2