- Haskell-Cafe - Haskell.org

Re: ANN: System.FilePath 0.10
by Simon Marlow 08 Nov '06

08 Nov '06

Neil Mitchell wrote: > ANNOUNCEMENT: > > I am hereby announcing System.FilePath 0.10, which hopefully is pretty > close to final now. This library manipulates FilePath's correctly on > both Posix and Windows. > > http://www-users.cs.york.ac.uk/~ndm/projects/libraries.php#filepath > > (Includes a darcs repo, a .tar.gz, haddock documentation etc) > > In this version I have made reasonably large changes: > > * Lots of functions gone (temporary file handling, canonicalization, > drive manipulation, directory creation, directory enumeration) - > pretty much down to only pure (non-IO methods) left. > > * 3 new methods (asFile, isFile, asDirectory - look up the docs for > their meanings, but they are pretty small) > > * Renamed functions to follow the scheme replace/take/drop instead of > set/get/drop - as suggested by Simon Marlow (since set/get implies > state operations in Haskell) Looks good! I have a few small further suggestions: - remove addFileName: it does the same thing as combine, or rather the difference is subtle and not mentioned in the docs. It's subsumed by combine, anyway. - remove isDirectory. I think its presence is confusing, e.g forall x. isDirectory (takeDirectory x) == False! Also it's not really correct; "/bin/" means something subtly different to "/bin" on Unix systems. Similarly isFile, asFile, asDirectory could be removed, I think. - Use the terminology "search path" consistently for anything to do with $PATH. i.e. fileSeparator => searchPathSeparator, isFileSeparator => isSearchPathSeparator, splitFiles => splitSearchPath also, move fileSeparator, isFileSeparator into the $PATH section in the docs (or change "basic functions" to "separator predicates"). - remove splitPath: splitDirectories is enough. I'd rename it to splitPathComponents, though. - shortPath => relativeToCurrentDirectory shortPathWith => makeRelativePath Cheers, Simon

2 1

Re: Livecoding music in Haskell
by Rohan Drape 08 Nov '06

08 Nov '06

On Tue Nov 7 16:32:11 EST 2006, alex wrote: > Latency I deal with by calculating everything a second or so ahead of > time, and timestamping my OSC packets with times in the future. Then on > the other side I have some scheduling stuff to trigger sounds at the > right moment, for example in SuperCollider's sclang: A second seems excessive? Working directly with ghc <-> scsynth latencies of ~ 0.075 do not seem to be and issue with even relatively heavy scheduling loads. > response = { > arg time, responder, message; > if (message[1] == 'on', > { > SystemClock.sched(time - Date.getDate.rawSeconds, > {Synth("noisebox", > [\lgain, message[2] / 100, > \rgain, message[3] / 100, > \ts, message[4] / 100, > \browndel, message[5] / 100, > \filter, message[6], > \envtype, message[7] > ] > ); nil; > }; > ); > }); > }; > o = OSCresponder(nil, '/noise', response); > o.add; Even sclang, remarkable as it is, will need to be sending time-stamped bundles for reliable sample-accurate timing? Even to avoid perceptible jitter under high load? Regards, Rohan

2 2

Fun with Num instances of functions
by Henning Thielemann 08 Nov '06

08 Nov '06

Some people have argued, that Num instances of (->) would be nice in order to add functions nicely, say for f, g :: Num a => b -> a you would define (f+g) x = f x + g x With an according definition of fromInteger fromInteger = const numeric literals would also denote constant functions. This allows f+2 == \x -> f x + 2 . Even nicer, the mathematically established notation of omitting the multiplication dot 2(x+y) :: Integer will now be parsed by a Haskell compiler to the most obvious meaning 2 :: Integer ! :-)

1 0

Re: Fractional/negative fixity?
by Lennart Augustsson 08 Nov '06

08 Nov '06

On Nov 7, 2006, at 11:47 , apfelmus(a)quantentunnel.de wrote: > Henning Thielemann wrote: >> On Tue, 7 Nov 2006, Simon Marlow wrote: >> >>> I'd support fractional and negative fixity. It's a simple change to >>> make, but we also have to adopt >>> >>> http://hackage.haskell.org/cgi-bin/haskell-prime/trac.cgi/wiki/ >>> FixityResolution >>> >>> I've added the proposal to the end of that page. In fact, the page >>> already mentioned that we could generalise fixity levels, but it >>> didn't >>> mention fractional or negative values being allowed. >> >> Maybe that page could also mention earlier proposals and the >> solutions >> without precedence numbers. I prefer the non-numeric approach with >> rules >> like "(<) binds more tightly than (&&)", because it says what is >> intended >> and it allows to make things unrelated that are unrelated, e.g. infix >> operators from different libraries. Consequently a precedence >> relation to >> general infix operators like ($) and (.) had be defined in each >> library. > > I think that computable real fixity levels are useful, too. A further > step to complex numbers is not advised because those cannot be > ordered. But ordering of the computable reals is not computable. So it could cause the compiler to loop during parsing. :) -- Lennart

2 1

Livecoding music in Haskell
by dons＠cse.unsw.edu.au 08 Nov '06

08 Nov '06

Alex McLean has kindly put up a screencast of him creating *music via live coding in Haskell* ! http://doc.gold.ac.uk/~ma503am/alex/haskellmusic And a .avi version of the screencast, playable in mplayer (for those not flash inclined). http://yaxu.org/20/hs.avi The code is running in hs-plugins, and being reloaded on the fly as he edits the source, changing the rhythms that are produced. More on this on Alex's blog: http://doc.gold.ac.uk/~ma503am/alex/ Cool stuff! -- Don

4 4

Permutation with k levels
by Nuno Pinto 08 Nov '06

08 Nov '06

Hi all, I am coding a zip application (using huffman algorithm) for academic reasons. In the process i needed a permute function that i coded but disliked a lot.. I went to the internet looking for a good generic permute algorithm in haskell the best one i found was not generic at all: import List perms [] = [[]] perms (x:xs) = [ p ++ [x] ++ s | xs' <- perms xs , (p, s) <- zip (inits xs') (tails xs') ] I also found information regarding this subject in: http://www.haskell.org/hawiki/PermutationExample What am i coding in specific? I receive a list in the form: -- l1 is a pair of the identifier and the associated probability l1 = [("A",0.6),("B",0.2)] I must return the permutation with k levels; for example: -- permute l k = ... -- should return permute l1 0 = [] permute l1 1 = l1 permute l2 2 = [("AA",0.64),("AB",0.16),("BA",0.16),("BB",0.04)] permute l3 3 = [("AAA", Pa*Pa*Pa), ("AAB",Pa*Pa*Pb),("ABA",...),("ABB",...),("BAA",...),("BAB",...),("BBA",...),("BBB",...)] --where: -- 0.64 = Pa*Pa -- 0.16 = Pa*Pb -- 0.04 = Pb*Pb All of my friend are developing this in c... Of course its easier but i have enough of c and c# at work, so I'm doing this in haskell, the way i like it :) For all interested in huffman coding: http://en.wikipedia.org/wiki/Huffman_coding Thanks in advance for the help, and greetings to all! Nuno P.s. Follows the code i developed until now.. Its open source :P Just hope no-one submit the same work as i did :P -- <resumo>-- Este modulo define uma ferramenta de compressão usando para o -- efeito o algoritmo de Huffman.---- HZip quer dizer isso mesmo: HuffmanZip.-- </resumo>module HZip where import List -- #region Notas-- . Ver parte de compressão/rendimento pois pode ter boas dicas para eficiência.-- #endregion -- #region Constantes para efeitos de teste.-- <resumo>-- Listas usadas para efeito de teste.-- </resumo> l1 = [("b",0.15),("d",0.08),("f",0.02),("g",0.01),("e",0.08),("c",0.15),("a",0.5),("h",0.01)] l2 = [("a",0.8),("b",0.2)]-- #endregion -- #region Funções Auxiliares-- <resumo>-- Função que testa a convergência de funções.-- Quando o valor da próxima iteração é igual ao da anterior-- devolve o resultado respectivo.---- Da autoria de jas<at>di<dot>uminho<dot>pt-- </resumo>-- <variavel termo='f'>-- A função a aplicar recursivamente.-- </variavel>-- <variavel termo='s'>-- A solução actual do problema.-- </variavel>-- <devolve>-- O resultado final da operação.-- </devolve>-- limit :: (a -> a) -> a -> a limit f s | s == next = s | otherwise = limit f next where next = f s -- <resumo>-- Calcula a metade das probabilidades.-- </resumo>-- <variavel termo='l'>-- A lista de probabilidades.-- </variavel>-- <devolve>-- O total das probabilidades a dividir por 2.-- </devolve> metade l = (sum l) / 2 -- <resumo>-- Devolve o primeiro elemento de um tuplo de 3.-- </resumo>-- <variavel termo='t'>-- O tuplo.-- </variavel>-- <devolve>-- O primeiro elemento.-- </devolve> fst3 (a,_,_) = a -- <resumo>-- Devolve o segundo elemento de um tuplo de 3.-- </resumo>-- <variavel termo='t'>-- O tuplo.-- </variavel>-- <devolve>-- O segundo elemento.-- </devolve> snd3 (_,b,_) = b -- <resumo>-- Devolve o terceiro elemento de um tuplo de 3.-- </resumo>-- <variavel termo='t'>-- O tuplo.-- </variavel>-- <devolve>-- O terceiro elemento.-- </devolve> trd3 (_,_,c) = c-- #endregion -- #region Funções: Teoria da informação-- <resumo>-- Calcula a quantidade de informação de uma determinada mensagem.-- </resumo>-- <variavel termo='p'>-- A probabilidade da mensagem.-- </variavel>-- <devolve>-- A quantidade de informação da mensagem.-- </devolve>-- i :: Float -> Float i p = logBase 2 (1/p) -- <resumo>-- Entropia, função que calcula a informação média por mensagem.-- </resumo>-- <variavel termo='l'>-- A lista de probabilidades.-- </variavel>-- <devolve>-- A informação média por mensagem.-- </devolve>-- h :: [Float] -> Float h l = sum $ map (\p -> if p == 0 then 0 else p * i p) l -- <resumo>-- Calcula o comprimento médio do código (N).-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- p -> Probabilidade do acontecimento.-- c -> Comprimento da palavra código.-- </variavel>-- <devolve>-- O comprimento médio do código.-- </devolve>-- n :: [(Float,Int)] -> Float n l = sum $ map (\(c,p) -> p * c) l -- <resumo>-- Desigualdade de Kraft.-- </resumo>-- <variavel termo='l'>-- A lista de comprimento das palavras código.-- </variavel>-- <devolve>-- True, se o código binário for univocamente decifravel-- False caso contrário.-- </devolve>-- kr :: [Int] -> Bool kr l = 1 >= sum ( map (\n -> 2^^(-n)) l ) -- <resumo>-- Algoritmo dos códigos de Huffman.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <devolve>-- Tuplo do tipo (t,n,b) em que:-- t -> Tabela de Huffman resultante.-- n -> Comprimento médio do código.-- b -> Se o código resultante é unívocamente decifravel.-- </devolve>-- huffman :: [(String,Float)] -> ([(String,Float,[Int])], Float, Float, Bool) huffman l = (tabHuffman,n lProbTam,kr lTamanhos) where lProbTam = map (\(c,p,b) -> (p,fromIntegral(length b))) tabHuffman lTamanhos = map (\(c,p,b) -> (length b)) tabHuffman tabHuffman = concat $ limit passo5 [map (\(c,p) -> (c,p,[])) (passo1 l)] -- <resumo>-- Ordena as mensagens por ordem decrescente de probabilidade.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <devolve>-- A lista ordenada por ordem decrescente de probabilidade.-- </devolve>-- passo1 :: [(String,Float)] -> [(String,Float)] passo1 l = sortBy (\(_,p1) (_,p2) -> compare p2 p1) l -- <resumo>-- Repete o calculo para cada um dos subconjuntos.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p,b) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- b -> Lista de inteiros com o binário correspondente.-- </variavel>-- <devolve>-- A lista ordenada por ordem decrescente de probabilidade.-- </devolve>-- passo5 :: [(String,Float,[Int])] -> [(String,Float,[Int])] passo5 l@(h:[]) = (passo234 0 (metade (map (\(_,p,_) -> p) h)) h (length h) [] []) passo5 l@(h:t) = (passo234 0 (metade (map (\(_,p,_) -> p) h)) h (length h) [] []) `union` (passo5 t) -- <resumo>-- Divide os subconjuntos cada um com apróximadamente métade da probabilidade-- mantendo a ordenação. Em seguida atribui o código binário e termina a codificação-- para o subconjunto se este tiver apenas um elemento.-- </resumo>-- <variavel termo='ac'>-- O acumulador de probabilidade.-- </variavel>-- <variavel termo='e'>-- Sublista a esquerda.-- </variavel>-- <variavel termo='d'>-- Sublista a direita.-- </variavel>-- <variavel termo='n'>-- Define o comportamento de paragem caso sublista tenha comprimento 1.-- </variavel>-- <variavel termo='l'>-- O calculo actual da tabela de huffman.-- </variavel>-- <devolve>-- Um passo da tabela de huffman.-- </devolve>-- passo234 :: Float -> Float -> [(String,Float,[Int])] -> Int -> [(String,Float,[Int])]-- -> [(String,Float,[Int])] -> [[(String,Float,[Int])]] passo234 _ _ [] _ e [] = [e] passo234 _ _ [] _ e d = [e]++[d] passo234 _ _ (h:t) 1 e d = passo234 0 0 [] 1 [h] d passo234 ac met l@((c,p,b):t) n [] d = passo234 (ac+p) met t n [(c,p,b++[0])] d passo234 ac met l@((c,p,b):t) _ e d | ac < met = passo234 (ac+p) met t 2 (e++[(c,p,b++[0])]) d |otherwise = passo234 (ac+p) met t 2 e (d++[(c,p,b++[1])]) -- <resumo>-- Codifica por blocos conforme um factor.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <variavel termo='k'>-- k = 1, codificação = 8 bits.-- k = 2, codificaçao = 16 bits.-- k = 3, codificação = 32 bits.-- k = n, cofificação = 2^(n+2) bits.-- </variavel>-- <devolve>-- A tabela de huffman associada,-- H (fonte),-- N,-- Se o codigo gerado é unívocamente decifravel.-- </devolve>-- permute deve ser subsituido por (permute l k) blocos l k = (fst3 tabHuffman, h (map snd l), (snd3 tabHuffman)/k, trd3 tabHuffman) where tabHuffman = huffman permute -- <resumo>-- Cria as permutações da de simbolos e calcula a probabilidade associada.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <variavel termo='k'>-- Número de niveis.-- </variavel>-- <devolve>-- Uma lista com os novos simbolos (codificação por blocos) e a respectiva-- probabilidade.-- </devolve> permute = [("aa",0.64),("ab",0.16),("ba",0.16),("bb",0.04)] -- <resumo>-- Calcula a compressão num determinado passo.-- </resumo>-- <variavel termo='l'>-- Lista do tipo (c,p) em que:-- c -> Caracter identificativo.-- p -> Probabilidade desse caracter acontecer.-- </variavel>-- <variavel termo='k'>-- Número do passo.-- </variavel>-- <devolve>-- Percentagem de compressão.-- </devolve> compressao l k = (nf - n_)/nf where nf = snd3 (huffman l) n_ = trd4 (blocos l k) trd4 (_,_,c,_) = c-- #endregion _________________________________________________________________ Windows Live Spaces is here! It’s easy to create your own personal Web site. http://spaces.live.com/signup.aspx

5 5

Efficiency of bang patterns
by Chad Scherrer 08 Nov '06

08 Nov '06

I'm curious about the implementation of bang patterns, and the implications for performance. Previously on this list, Lemmih has pointed out that throwing in an extra `seq` here and there to force strictness is a bad idea, unless you do it very carefully. He points out that the strictness analyzer will catch a lot of cases without a need for seq. But the approach of compiling without any `seq`s, looking for leaks, and then adding them in one at a time seems tedious. There should be a more predictable, more uniform way of achieving strictness. Is it reasonable to promote a programming style where strictness is achieved using strictness annotations and bang patterns? I find it very appealing that the "!" syntax translates so nicely from type declarations to patterns. I had originally thought that every bang pattern was translated into a seq call, as a sort of preprocessing step, but from this page... http://hackage.haskell.org/trac/haskell-prime/wiki/BangPatterns ... is is clear that in many cases a bang pattern can be rewritten as a case statement, which seems to me an opportunity to avoid some code ugliness. In cases semantically distinct from a case statement, maybe something like the following could be done, or maybe is already... 1. Pass the expression to the strictness analyzer, without the bang pattern. 2. If it's already strict, great! We're done. 3. If not, add an extra seq call. Now, I'm no compiler expert (obviously, I suspect), and maybe I've misunderstood the role of the strictness analysis step. But being able to easily make things really strict seems pretty important, and there seem to be a lot of subtleties to using seq that make it difficult to tune for performance. -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

1 0

Announcements list
by Diego Navarro 07 Nov '06

07 Nov '06

There should be a separate, moderated Haskell-announcements list. I filter out haskell-cafe into a folder and read it separately from my main inbox, but I'd like to have important announcements directly into my inbox, and haskell(a)haskell.org still has some chatty questions-and-answers sessions. -- Diego Navarro/syntaxfree

3 2

[ghc 6.6] Where is FGL now?
by Stephane Bortzmeyer 07 Nov '06

07 Nov '06

In ghc 6.4, I used Data.Graph.Inductive (aka FGL): % ghc-pkg list /usr/lib/ghc-6.4/package.conf: ... fgl-5.2, ... In ghc 6.6, it seems it disappeared. ghc-pkg list does not show it, the compiler says "Could not find module `Data.Graph.Inductive'" but it is still documented in http://www.haskell.org/ghc/docs/latest/html/libraries/index.html and the ghc 6.6 changelog does not mention its removal.

1 1

Vectors and Matrices
by dBuchmann＠gmx.net 06 Nov '06

06 Nov '06

Is there a library implementing vectors and matrices in a possible elegant manner. Even perhaps with Tensor-/Kronecker-Product and Scalar-Product. greetings. _________________________________ dBuchmann(a)gmx.net; visit http://filzbits.de

2 1

Re: Haskell-Cafe Digest, Vol 39, Issue 6
by Chad Scherrer 06 Nov '06

06 Nov '06

Lemmih wrote: > Using 'seq' is generally a bad idea. It can worsen the performance if > not used carefully and GHCs strictness analyser is usually good > enough. Is GHC.Conc.pseq any better? Usually the whole point of making things more strict is to optimize performance for pieces you know will be evaluated anyway. It's frustrating if there's not a consistent way to do this that works well. Lately, I've been using lots of strictness annotations and bang patterns - are there non-obvious places this could slow things down? Would it be possible for the type system to distinguish at compile time whether something would need to be evaluated, and optimize away redundant `seq`s? Maybe this is what the strictness analyzer does already. Chad

4 4

Module visibility of data type constructors
by Slavomir Kaslev 06 Nov '06

06 Nov '06

Hello. I have a simple question for data type constructors visibility. Take a look: module Foo (Bar) where data Bar = Bar In ghc this allows me to use Bar, the type constructor, in another module, although it shouldn't be visible outside Foo. On the other hand, if I change Bar's definition as: data Bar = Baz Baz isn't visible outside Foo. Is this the correct behavior or is it bug in ghc? Cheers. -- Slavomir Kaslev

3 5

64bit code output is less optimized than 32bit in ghc?
by isto 06 Nov '06

06 Nov '06

Hi again, Still playing with the Mersenne Twister and here is the updated 64 bit version so that there are not so many constructor calls on next64 (together with updated compiling flags). I was wondering why different runs can have such different run times and the cause was found to be my system: also the C version running times can vary (usually 0.65 but sometimes 0.3). The 64 bit version took usually about 1.1 or 1.2 seconds while 32bit version required only 0.78 (against 0.65 with C for both 32 and 64 bit versions). Since the real work horse here is the next64 function, I took a look of Core. There seems to be an extra case-statement in 64bit version and this might explain the performance drop (about 6 or 7 lines below _DEFAULT text on both versions below). Relevant parts of the Core below, code attached. It is very possible that I'm missing something obvious here. So what is happening here? :) Thanks again for any comments! br, Isto -------------------------------------------- Core (32 and 64 nexts) Rec { Mersenne.$wnext64 :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word64 -> GHC.Prim.Int# -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, (GHC.Word.Word64, GHC.Base.Int) #) [GlobalId] [Arity 3 Str: DmdType LLL] Mersenne.$wnext64 = \ (w_s2Zq :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word64) (ww_s2Zt :: GHC.Prim.Int#) (w1_s2Zv :: GHC.Prim.State# GHC.Prim.RealWorld) -> case ww_s2Zt of ds_X2F1 { __DEFAULT -> case w_s2Zq of wild_a2Pp { Data.Array.Base.STUArray ds2_a2Pr ds3_a2Ps marr#_a2Pt -> case GHC.Prim.readWord64Array# @ GHC.Prim.RealWorld marr#_a2Pt ds_X2F1 w1_s2Zv of wild2_a2PA { (# s2#_a2PC, e#_a2PD #) -> (# s2#_a2PC, ((case lit_r34C of wild1_a2Ol { GHC.Word.W64# y#_a2On -> let { ww1_a2NY [Just L] :: GHC.Prim.Word# [Str: DmdType] ww1_a2NY = GHC.Prim.xor# e#_a2PD (GHC.Prim.and# (GHC.Prim.uncheckedShiftRL# e#_a2PD 29) __word 6148914691236517205) } in let { ww2_X2Q0 [Just L] :: GHC.Prim.Word# [Str: DmdType] ww2_X2Q0 = GHC.Prim.xor# ww1_a2NY (GHC.Prim.and# (GHC.Prim.uncheckedShiftL# ww1_a2NY 17) __word 8202884508482404352) } in let { ww3_X2QE [Just L] :: GHC.Prim.Word# [Str: DmdType] ww3_X2QE = GHC.Prim.xor# ww2_X2Q0 (GHC.Prim.and# (GHC.Prim.uncheckedShiftL# ww2_X2Q0 37) y#_a2On) } in GHC.Word.W64# (GHC.Prim.xor# ww3_X2QE (GHC.Prim.uncheckedShiftRL# ww3_X2QE 43)) }), (GHC.Base.I# (GHC.Prim.+# ds_X2F1 1))) #) } }; 312 -> case Mersenne.generateNumbers64 w_s2Zq w1_s2Zv of wild_a2DL { (# new_s_a2DN, a87_a2DO #) -> case Mersenne.$wnext64 w_s2Zq 0 new_s_a2DN of wild1_X2Fy { (# new_s1_X2FB, a871_X2FD #) -> case a871_X2FD of wild2_Xar { (w2_aU2, iN_aU3) -> (# new_s1_X2FB, wild2_Xar #) } } } } end Rec } Mersenne.next64 :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word64 -> GHC.Base.Int -> GHC.IOBase.IO (GHC.Word.Word64, GHC.Base.Int) [GlobalId] [Arity 3 Worker Mersenne.$wnext64 Str: DmdType LU(L)L] Mersenne.next64 = __inline_me (\ (w_s2Zq :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word64) (w1_s2Zr :: GHC.Base.Int) (w2_s2Zv :: GHC.Prim.State# GHC.Prim.RealWorld) -> case w1_s2Zr of w3_X30R { GHC.Base.I# ww_s2Zt -> Mersenne.$wnext64 w_s2Zq ww_s2Zt w2_s2Zv }) Rec { Mersenne.$wnext32 :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word32 -> GHC.Prim.Int# -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, (GHC.Word.Word32, GHC.Base.Int) #) [GlobalId] [Arity 3 NoCafRefs Str: DmdType LLL] Mersenne.$wnext32 = \ (w_s2YJ :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word32) (ww_s2YM :: GHC.Prim.Int#) (w1_s2YO :: GHC.Prim.State# GHC.Prim.RealWorld) -> case ww_s2YM of ds_X2CS { __DEFAULT -> case w_s2YJ of wild_a2Hd { Data.Array.Base.STUArray ds2_a2Hf ds3_a2Hj marr#_a2Hk -> case GHC.Prim.readWord32Array# @ GHC.Prim.RealWorld marr#_a2Hk ds_X2CS w1_s2YO of wild2_a2Hr { (# s2#_a2Ht, e#_a2Hu #) -> (# s2#_a2Ht, ((let { ww1_a2Fr [Just L] :: GHC.Prim.Word# [Str: DmdType] ww1_a2Fr = GHC.Prim.xor# e#_a2Hu (GHC.Prim.uncheckedShiftRL# e#_a2Hu 11) } in let { ww2_X2GX [Just L] :: GHC.Prim.Word# [Str: DmdType] ww2_X2GX = GHC.Prim.xor# ww1_a2Fr (GHC.Prim.and# (GHC.Prim.narrow32Word# (GHC.Prim.uncheckedShiftL# ww1_a2Fr 7)) __word 2636928640) } in let { ww3_X2Hp [Just L] :: GHC.Prim.Word# [Str: DmdType] ww3_X2Hp = GHC.Prim.xor# ww2_X2GX (GHC.Prim.and# (GHC.Prim.narrow32Word# (GHC.Prim.uncheckedShiftL# ww2_X2GX 15)) __word 4022730752) } in GHC.Word.W32# (GHC.Prim.xor# ww3_X2Hp (GHC.Prim.uncheckedShiftRL# ww3_X2Hp 18))), (GHC.Base.I# (GHC.Prim.+# ds_X2CS 1))) #) } }; 624 -> case Mersenne.generateNumbers32 w_s2YJ w1_s2YO of wild_a2DL { (# new_s_a2DN, a87_a2DO #) -> case Mersenne.$wnext32 w_s2YJ 0 new_s_a2DN of wild1_X2F2 { (# new_s1_X2F5, a871_X2F7 #) -> case a871_X2F7 of wild2_X80 { (w2_aSH, iN_aSI) -> (# new_s1_X2F5, wild2_X80 #) } } } } end Rec } Mersenne.next32 :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word32 -> GHC.Base.Int -> GHC.IOBase.IO (GHC.Word.Word32, GHC.Base.Int) [GlobalId] [Arity 3 Worker Mersenne.$wnext32 NoCafRefs Str: DmdType LU(L)L] Mersenne.next32 = __inline_me (\ (w_s2YJ :: Data.Array.IO.Internals.IOUArray GHC.Base.Int GHC.Word.Word32) (w1_s2YK :: GHC.Base.Int) (w2_s2YO :: GHC.Prim.State# GHC.Prim.RealWorld) -> case w1_s2YK of w3_X2ZO { GHC.Base.I# ww_s2YM -> Mersenne.$wnext32 w_s2YJ ww_s2YM w2_s2YO })

1 0

Unicode strings
by Pupeno 06 Nov '06

06 Nov '06

Hello, I am trying to make a program that outputs some Unicode characters but the output doesn't match what I try to print. Attached is a little test program. It tries to print the arrows "←↑→↓" but instead it outputs "\220\221\222\223" (that is, character number 220, then 221, then 222). I've also tried writing the Unicode code points (although GHC 6.6 should deal just fine with Unicode source code) and I get the same result. In case anybody wants to try, this would be the string: "\8592\8593\8594\8595". I am also attaching the output file, you can see that the contents are not right. Any ideas what am I doing wrong here ? Thank you. -- Pupeno <pupeno(a)pupeno.com> (http://pupeno.com)

4 3

A restricted subset of CPP included in a revision of Haskell 98
by Brian Smith 05 Nov '06

05 Nov '06

Hi, I find it strange that right now almost every Haskell program directly or indirectly (through FPTOOLS) depends on CPP, yet there is no effort to replace CPP with something better or standardize its usage in Haskell. According to the following document, and my own limited experience in reading Haskell code, CPP is the most frequently used extension: http://hackage.haskell.org/trac/haskell-prime/wiki/HaskellExtensions I think that if we accepted that CPP was part of the language, we could then place some restrictions on its use to facilitate easier parsing. Here are some suggestions, off the top of my head: * #define can only be used for parameterless definitions * #define'd symbols are only visible to the preprocessor * #define can only give a symbol a value that is a valid preprocessor expression * #define can only appear above the module declaration * a preprocessor symbol, once defined, cannot be undefined or redefined * #include and #undef are prohibited * The preprocessor can only be used at the top level. In particular, a prepropcessor conditional, #error, #warn, #line would not be allowed within the export list or within a top-level binding. * A Haskell program must assume that any top-level symbol definitions are constant over the entire program. For example, a program must not depend on having one module compiled with one set of command-line preprocessor symbol bindings and another module defined with a different set of bindings. * preprocessor directives must obey Haskell's layout rules. For example, an #if cannot be indented more than the bindings it contains. The result would be: * Syntax can be fully checked without knowing the values of any preprocessor symbols. * Preprocessor syntax can be added easily to a Haskell parser's BNF description of Haskell. * No tool will need to support per-file/module preprocessor symbol bindings. Again, all this is just off the top of my head. I am curious about what problems these restrictions might cause, especially for existing programs. I know that GHC itself uses some features that would be prohibited here. But, GHC is really difficult for tools to handle even with these restrictions on its source code. For now, I am more interested in the libraries in FPTOOLS and users' programs. What libraries/programs cannot easily be reorganizated to meet these restrictions? I suspect "#define'd symbols are only visible to the preprocessor" would be the most troublesome one. Thanks, Brian

7 9

Re[2]: [Haskell] GHC inferred type different for pointed/point-free defs?
by Bulat Ziganshin 04 Nov '06

04 Nov '06

Hello Dan, Saturday, November 4, 2006, 3:49:13 AM, you wrote: > You might want to rename your (&&&) and (|||), though, since they clash > with those defined in Control.Arrow. > I found that by defining (???) then way I did, I could use > (Control.Arrow.|||) as-is for the second part. i just not use arrows because i don't understand them. my definitions of "&&&" and "|||" is like those in C/perl/ruby and most times i use them alone: debugging &&& debug_info, first_time ||| putStrLn "" in the far future, i will be glad to see && and || redefined in this way (or some like this; it should just provide ruby's look&feel plus extensibility). although for my own program this may be solved by just not importing Prelude. hmmm, i should think about it.. but && and || functions is not exactly the same as ?: operator (nor in C, nor in standard Haskell, nor in my implementation). with these operations condition is tested _twice_ and if second argument has "false" value, third one will be returned anyway: True && False || True => True True ? False : True => False btw, it may be extended slightly more by adding application version: a &&. f = a &&& (f a) example: str &&. ("debug info: "++) now such function named unlessNull that is not so neat -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0

Re: [Haskell] GHC inferred type different for pointed/point-free defs?
by Neil Mitchell 04 Nov '06

04 Nov '06

Hi, You probably want to read up on: Monomorphism restriction (I don't think this applies here, but I'm never too sure!): http://www.haskell.org/hawiki/MonomorphismRestriction Defaulting: http://www.haskell.org/onlinereport/decls.html#sect4.3.4 I don't understand either to any great degree, but when points free starts changing things, its usually one of those two kicking in. And as a side note, haskell@ tends to be used more for announcements, and haskell-cafe@ is used more for asking questions etc. Thanks Neil On 11/3/06, Dan Weston <westondan(a)imageworks.com> wrote: > Help! One of two things is going on: > > 1) I don't understand what I'm doing > 2) GHC is inferring different types for pointed and > point-free function definition. > > I wanted to define Haskell equivalents to the C ternary operator. > Basically, predicate ??? doIfTrue ||| doIfFalse > > For some reason, though, in GHC 6.4 and 6.7, the types > inferred for abs1 and ab2 (defined below) are different: > > *Main> :t abs1 > abs1 :: (Num a, Ord a) => a -> a > > *Main> :t abs2 > abs2 :: Integer -> Integer > > How is abs2 less general just because I use point-free > notation instead of pointed notation? They should have the same > type, no? I'm stumped... > > > import Control.Arrow > > import Data.Either > > > > infix 1 ?, ??, ???, ???? > > > > (?) True = Left > > (?) False = Right > > > > (??) True = Left . fst > > (??) False = Right . snd > > > > p ??? q = (p &&& arr id) >>> uncurry (?) >>> q > > p ???? q = (p &&& arr id) >>> uncurry (??) >>> q > > > > abs1 x = (< 0) ??? negate ||| id $ x > > abs2 = (< 0) ??? negate ||| id > > > > checks :: [Bool] > > checks = > > [ > > (True ? 3 ) == (Left 3), > > (False ? 4 ) == (Right 4), > > (True ?? (3,4)) == (Left 3), > > (False ?? (3,4)) == (Right 4), > > (even ??? (`div` 2) ||| (+1).(*3) $ 3 ) == ( 10), > > (even ??? (`div` 2) ||| (+1).(*3) $ 4 ) == ( 2), > > (uncurry (==) ???? (+1) ||| (*3) $ (3,3)) == ( 4), > > (uncurry (==) ???? (+1) ||| (*3) $ (3,4)) == ( 12), > > (uncurry (==) ???? (+1) +++ (*3) $ (3,3)) == (Left 4), > > (uncurry (==) ???? (+1) +++ (*3) $ (3,4)) == (Right 12), > > (abs1 5 ) == ( 5), > > (abs1 (-5) ) == ( 5), > > (abs2 5 ) == ( 5), > > (abs2 (-5) ) == ( 5) > > ] > > > > main = print (and checks) > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell >

1 0

Finding Memory Leaks
by Matthew Bromberg 04 Nov '06

04 Nov '06

I have a rather complex Haskell program that performs an engineering simulation using a lot of large complex valued matrices. The imperative components of the simulation are written in C and interfaced into Haskell which handles the higher level logic. This has served me fairly well, and I've been pleased with both the development style and the performance of my code. However I've run into a fairly major issue with an unresolvable memory leak in the Haskell code. The memory leak is apparent since both private allocated bytes and page file bytes associated with the process increase linearly over time while the process is running. Eventually it causes the process to crash. I believe it's in the Haskell code because I have replaced malloc, free, realloc etc. in the C code with a memory leak detector and the C code appears to free all allocated resources. I also know that the memory leak is due to unmatched free's from a call to malloc from one of the windows XP system libraries. Unfortunately GHC's heap profiler does not reveal the memory leak. All my code is compiled using the -prof -auto flag and then run using +RTS -hc -RTS. The resulting plots do not show a linear increase in heap usage, although the Windows XP operating system does report such an increase. This leaves me in a difficult position in terms of finding the offending code. I am currently resorting to commenting out code line by line, but it's very tedious since I have to preserve the state functionality of the code to get it to run. Is there a way to compile Haskell into C using GHC and then forcing the C code to hook up to the memory leak detecting versions of malloc? I know that GHC can produce intermediary C code, but I have no idea how to access it and how to setup all the run time libraries etc, so that I can compile the C code separately. Any advice for me in this situation would be appreciated.

4 5

[Haskell-cafe]Prime Generator time limit exceeded
by alaiyeshi 04 Nov '06

04 Nov '06

Hi I'm new to Haskell. I found this site on the Haskell wiki https://www.spoj.pl. But I got some trouble on trying to solve the problem titled "Prime Generator" https://www.spoj.pl/problems/PRIME1. The online-judge system tells me "time limit excedded" Would you be so kind to tell me how to make it more faster? And any other suggestion is welcome. Thanks in advance. --------------------------------------Code begin------------------------------------------------------------ module Main where import IO import List main = do input_size<-getLine content<-get_contents (read input_size) mapM_ (\r-> do mapM_ (print) (primeGenerator (parse r)); putStrLn "") content get_contents n | n == 0 = return [] | otherwise = do content<-getLine rests<-get_contents (n-1) return ([content]++rests) primeGenerator [start,end] = [x | x<-[start..end], all (== 1) (map (gcd x) [2..(x-1)]), x/=1] parse s = unfoldr (\x-> case x of [] -> Nothing _ -> Just (head (reads x))) s -------------------------------Code ends-------------------------------------------------------------------------------- (BTW: I'm new to this mailling list also, forgive my rudeness if I am, and forgive my poor English)

5 11

Cost of seq (sorry about the old subject)
by Chad Scherrer 03 Nov '06

03 Nov '06

On 11/2/06, Bulat Ziganshin <bulat.ziganshin(a)gmail.com> wrote: > Hello Chad, > > Thursday, November 2, 2006, 8:49:17 PM, you [Chad] wrote: > > Would it be possible for the type system to distinguish at compile > > time whether something would need to be evaluated, and optimize away > > redundant `seq`s? Maybe this is what the strictness analyzer does > > already. > > afaik, seq cost is zero (except for evaluating expressions, of course) > So if x has already been evaluated, does x `seq` y evaluate just as quickly as y alone, or does it require extra cycles to make sure x has been evaluated? -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

2 1

Re: [Haskell-cafe] Class
by Slavomir Kaslev 03 Nov '06

03 Nov '06

On 11/2/06, Sebastian Sylvan <sylvan(a)student.chalmers.se> wrote: > On 11/2/06, Slavomir Kaslev <slavomir.kaslev(a)gmail.com> wrote: > > Little by little, I think I am getting closer. > > > > class Show a => Visible a where > > toString :: a -> String > > toString = show > > size :: a -> Int > > size = length . show > > > > Is just declaration, not definition. It doesn't define anything, even > > though it has default implementations for toString and size one still > > needs to define instance of it. Right? > > > > As Sebastian Sylvan proposed, I probably need something like this: > > > > class Visible a where > > toString :: a -> String > > size :: a -> Int > > > > instance Show a => Visible a where > > toString = show > > size = length . show > > > > But it seems ghc doesn't like instance definitions like 'instance Show > > a => Visible a where ...'. Why? > > This is not Haskell98 since instance declarations of this form could > cause the type checker to go into an infinite loop. This particular > one is okay, though, but you have to start ghc with > -fallow-undecidable-instances and -fglasgow-exts I'm afraid. > > > -- > Sebastian Sylvan > +46(0)736-818655 > UIN: 44640862 > Thanks, Sebastian. That was helpful. Are there any papers on the subject? -- Slavomir Kaslev

3 3

How to improve speed? (MersenneTwister is several times slower than C version)
by isto 03 Nov '06

03 Nov '06

Hi all, On HaWiki was an announcement of MersenneTwister made by Lennart Augustsson. On a typical run to find out 10000000th rnd num the output is (code shown below): $ time ./testMTla Testing Mersenne Twister. Result is [3063349438] real 0m4.925s user 0m4.856s I was exercising with the very same algorithm and tried to make it efficient (by using IOUArray): now a typical run looks like (code shown below): $ time ./testMT Testing Mersenne Twister. 3063349438 real 0m3.032s user 0m3.004s The original C-version (modified so that only the last number is shown) gives typically $ time ./mt19937ar outputs of genrand_int32() 3063349438 real 0m0.624s user 0m0.616s Results are similar with 64 bit IOUArray against 64 bit C variant. C seems to work about 5 to 10 times faster in this case. I have tried to do different things but now I'm stuck. unsafeRead and unsafeWrite improved a bit the lazy (STUArray-version) and IOUArray-versions but not very much. I took a look of Core file but then, I'm not sure where the boxed values are ok. E.g. should IOUArray Int Word64 be replaced with something else? Any hints and comments on how to improve the efficiency and make everything better will be appreciated a lot! br, Isto ----------------------------- testMTla.hs (MersenneTwister, see HaWiki) module Main where -- ghc -O3 -optc-O3 -optc-ffast-math -fexcess-precision --make testMTla import MersenneTwister main = do putStrLn "Testing Mersenne Twister." let mt = mersenneTwister 100 w = take 1 (drop 9999999 mt) -- w = take 1 (drop 99 mt) putStrLn $ "Result is " ++ (show w) ----------------------------- ----------------------------- testMT.hs module Main where -- Compile eg with -- ghc -O3 -optc-O3 -optc-ffast-math -fexcess-precision --make testMT import Mersenne genRNums32 :: MT32 -> Int -> IO (MT32) genRNums32 mt nCnt = gRN mt nCnt where gRN :: MT32 -> Int -> IO (MT32) gRN mt nCnt | mt `seq` nCnt `seq` False = undefined gRN mt 1 = do (r,mt') <- next32 mt putStrLn $ (show r) return mt' gRN mt nCnt = do (r,mt') <- next32 mt gRN mt' $! (nCnt-1) main = do putStrLn "Testing Mersenne Twister." mt32 <- initialiseGenerator32 100 genRNums32 mt32 10000000 ----------------------------- ----------------------------- Mersenne.hs (sorry for linewraps) module Mersenne where import Data.Bits import Data.Word import Data.Array.Base import Data.Array.MArray import Data.Array.IO -- import System.Random data MT32 = MT32 (IOUArray Int Word32) Int data MT64 = MT64 (IOUArray Int Word64) Int last32bitsof :: Word32 -> Word32 last32bitsof a = a .&. 0xffffffff -- == (2^32-1) lm32 = 0x7fffffff :: Word32 um32 = 0x80000000 :: Word32 mA32 = 0x9908b0df :: Word32 -- == 2567483615 -- Array of length 624. initialiseGenerator32 :: Int -> IO MT32 initialiseGenerator32 seed = do let s = last32bitsof (fromIntegral seed)::Word32 mt <- newArray (0,623) (0::Word32) unsafeWrite mt 0 s iG mt s 1 mt' <- generateNumbers32 mt return (MT32 mt' 0) where iG :: (IOUArray Int Word32) -> Word32 -> Int -> IO (IOUArray Int Word32) iG mt lastNro n | n == 624 = return mt | otherwise = do let n1 = lastNro `xor` (shiftR lastNro 30) new = (1812433253 * n1 + (fromIntegral n)::Word32) unsafeWrite mt n new iG mt new (n+1) generateNumbers32 :: (IOUArray Int Word32) -> IO (IOUArray Int Word32) generateNumbers32 mt = gLoop 0 mt where gLoop :: Int -> (IOUArray Int Word32) -> IO (IOUArray Int Word32) gLoop i mt | i==623 = do wL <- unsafeRead mt 623 w0 <- unsafeRead mt 0 w396 <- unsafeRead mt 396 let y = (wL .&. um32) .|. (w0 .&. lm32) :: Word32 if even y then unsafeWrite mt 623 (w396 `xor` (shiftR y 1)) else unsafeWrite mt 623 (w396 `xor` (shiftR y 1) `xor` mA32) return mt | otherwise = do wi <- unsafeRead mt i wi1 <- unsafeRead mt (i+1) w3 <- unsafeRead mt ((i+397) `mod` 624) let y = (wi .&. um32) .|. (wi1 .&. lm32) if even y then unsafeWrite mt i (w3 `xor` (shiftR y 1)) else unsafeWrite mt i (w3 `xor` (shiftR y 1) `xor` mA32) gLoop (i+1) mt next32 :: MT32 -> IO (Word32, MT32) next32 (MT32 mt i) | i >= 624 = do mt' <- generateNumbers32 mt let m = MT32 mt' (i `mod` 624) (w,m') <- next32 m return (w,m') | otherwise = do y <- unsafeRead mt i let y1 = y `xor` (shiftR y 11) y2 = y1 `xor` ((shiftL y1 7 ) .&. 0x9d2c5680) -- == 2636928640 y3 = y2 `xor` ((shiftL y2 15) .&. 0xefc60000) -- == 4022730752 y4 = y3 `xor` (shiftR y3 18) return $ (y4, MT32 mt (i+1)) mA64 = 0xB5026F5AA96619E9 :: Word64 um64 = 0xFFFFFFFF80000000 :: Word64 lm64 = 0x7FFFFFFF :: Word64 initialiseGenerator64 :: Int -> IO (MT64) initialiseGenerator64 seed = do let s = (fromIntegral seed)::Word64 mt <- newArray (0,311) (0::Word64) unsafeWrite mt 0 s iG mt s 1 generateNumbers64 mt return (MT64 mt 0) where iG :: (IOUArray Int Word64) -> Word64 -> Int -> IO (IOUArray Int Word64) iG mt lN i | mt `seq` lN `seq` i `seq` False = undefined iG mt lastNro 312 = return mt iG mt lastNro n = do let n1 = lastNro `xor` (shiftR lastNro 62) new = (6364136223846793005 * n1 + (fromIntegral n)::Word64) unsafeWrite mt n new iG mt new $! (n+1) generateNumbers64 :: (IOUArray Int Word64) -> IO () generateNumbers64 mt = gLoop 0 where gLoop :: Int -> IO () gLoop i | i `seq` False = undefined gLoop 311 = do wL <- unsafeRead mt 311 w0 <- unsafeRead mt 0 w155 <- unsafeRead mt 155 let y = (wL .&. um64) .|. (w0 .&. lm64) :: Word64 if even y then unsafeWrite mt 311 (w155 `xor` (shiftR y 1)) else unsafeWrite mt 311 (w155 `xor` (shiftR y 1) `xor` mA64) return () gLoop i = do wi <- unsafeRead mt i wi1 <- unsafeRead mt (i+1) w3 <- unsafeRead mt ((i+156) `mod` 312) let y = (wi .&. um64) .|. (wi1 .&. lm64) if even y then unsafeWrite mt i (w3 `xor` (shiftR y 1)) else unsafeWrite mt i (w3 `xor` (shiftR y 1) `xor` mA64) gLoop $! (i+1) next64 :: MT64 -> IO (Word64, MT64) next64 (MT64 mt 312) = do generateNumbers64 mt let m = MT64 mt 0 (w,m') <- next64 m return (w,m') next64 (MT64 mt i) = do y <- unsafeRead mt i let y1 = y `xor` ((shiftR y 29) .&. 0x5555555555555555) y2 = y1 `xor` ((shiftL y1 17) .&. 0x71D67FFFEDA60000) y3 = y2 `xor` ((shiftL y2 37) .&. 0xFFF7EEE000000000) y4 = y3 `xor` (shiftR y3 43) return $! (y4, MT64 mt (i+1))

5 14

Non-integer part of a Double
by Maurício 03 Nov '06

03 Nov '06

Hi, Is there a function to get that? I'm using \x -> x - fromIntegral(floor x) since I was not able to find something better, but I guess I have missed something in the standard library since there are functions with similar funcionality. Thanks, Maurício

3 3

Fwd: [Haskell-cafe] Class
by Slavomir Kaslev 03 Nov '06

03 Nov '06

Little by little, I think I am getting closer. class Show a => Visible a where toString :: a -> String toString = show size :: a -> Int size = length . show Is just declaration, not definition. It doesn't define anything, even though it has default implementations for toString and size one still needs to define instance of it. Right? As Sebastian Sylvan proposed, I probably need something like this: class Visible a where toString :: a -> String size :: a -> Int instance Show a => Visible a where toString = show size = length . show But it seems ghc doesn't like instance definitions like 'instance Show a => Visible a where ...'. Why? -- Slavomir Kaslev

2 1

Re: [Haskell-cafe] Class
by Slavomir Kaslev 03 Nov '06

03 Nov '06

On 11/2/06, Sebastian Sylvan <sylvan(a)student.chalmers.se> wrote: > On 11/2/06, Slavomir Kaslev <slavomir.kaslev(a)gmail.com> wrote: > > > > > Visible 'subclasses' Show. Doesn't this mean that Visible should be > > defined for all types with Show instances? > > No, it just means that any type that you want to instantiate in > Visible needs to also have a Show instance (is this a restriction you > really want? See below). Well, yes that's what I meant. I want class Visible for objects that have Show instance and I want to be able to use this Show instance in the definition of Visible. Again this is not some practical example, I am just trying to grasp Haskell classes and instances. > > You could do something like > > instance Show a => Visible a > > (the default implementations that you provided in the class should be > enough, you could possibly move the implementations to the "Show > instance" and remove the Show super class from the Visible class - > then you could make even non-Show types instances of Visible without > having to define their instance for Show as well). > > /S > > > -- > Sebastian Sylvan > +46(0)736-818655 > UIN: 44640862 > This doesn't work either: import List class Visible a where toString :: a -> String size :: a -> Int instance Show a => Visible a where toString = show size = length . show instance Visible a => Visible [a] where toString = concat . map toString size = foldl (+) 0 . map size vSort :: (Visible a, Ord a) => [a] -> String vSort = toString . List.sort s = vSort [1..3] gives: Illegal instance declaration for `Visible a' (The instance type must be of form (T a b c) where T is not a synonym, and a,b,c are distinct type variables) In the instance declaration for `Visible a' Failed, modules loaded: none. at instance Show a => Visible a where. Probably I should reconsider my expectations? How should something like this designed? -- Slavomir Kaslev

2 3

Decorating a list of strings
by Steve Schafer 03 Nov '06

03 Nov '06

I have a list of text strings: ["Alice", "Bob", "Cindy", "Bob", "Bob", "Dave", "Cindy"] As you can see, some of the strings occur only once; others appear two or more times. I would like to end up with a new list, according to the following rules: 1) If a string occurs only once in the original list, then that string appears unchanged in the new list. 2) If a string occurs more than once in the original list, then each occurrences of that string is "decorated" with a numerical suffix indicating its relative position among its peers. In the case of the above list, the result of applying these rules would be: ["Alice", "Bob:1", "Cindy:1", "Bob:2", "Bob:3", "Dave", "Cindy:2"] So, how do we do this? The straightforward approach is to traverse the list twice, once to build a table of repeat counts for the different strings, and a second time to generate the new list, based on the old list plus the table of repeat counts. Of course, it's possible to streamline this into a single traversal by building up a list of thunks at the same time as the table of repeat counts is generated, and then to resolve those thunks by applying them in one fell swoop to the table. But while this does _conceptually_ streamline the problem, it doesn't offer any practical improvement; it takes at least as much processing effort to resolve the thunks as it would to make a second pass through the list. Can we do better? I can't think of a way to do better, and my gut feeling is that there isn't one (in general, it's impossible to know whether the first element of the new list will be "Alice" or "Alice:1" until the entire original list has been traversed), but I thought I'd put the question out to the community to see if anyone had any brilliant insights. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/

3 3

Towards an IO-Comonad that preserves referential integry (was: "comonads, io" Jan 02, 2003)
by Sven Biedermann 03 Nov '06

03 Nov '06

Dear Haskellers, The OI Comonad in Richard Kieburtz' paper does break referential integrity, but he worte, that the implementation is just something "...to experiment with". In this papers he states, that a real OI needs special properties. For instance enableOI needs "...to have the effect of copying pointers to currently accessible IO resources, in effect duplicating the current IO environment." So, I wrote a simple OI-Comonad for stdin/stdout only, that preserves referential integrity. At least, my reasoning and the tests I made didn't reveal anything different. The code and some explanations are presented at the end of this mail. Haskellers: Could you review the solution, please? Does it really preserves referential integrity? Or am I completely wrong? Do you have any suggestions on generalizing the idea? I would be glad to hear from you! Best regards Sven Biedermann ---------------------------------------------------------------- The implementation is based on two ideas: 1) The OI outside world is modeled an infinite structure (OIReality) that keeps track effects created in the outside world. All "futures" of a reality at a point of "time" are remembered in a lazy fashion. So, if one probes on referential integrity, the structure will be re-iterated through, playing back already computed results. If a reality at some point of "time" isn't referenced any more, that reality will be reclaimed by the garbage collector. The following statement is an example, that no space leaks occur as long as a specific reality isn't remembered (stdPutStr builds on basic stdPutChar using the standard operators .>> and =>>): extract $ mkOI 'x' .>> (cycle ['A'..'z']) =>> oiPutStr Amazingly, extract $ mkOI 'x' .>> (cycle ['A'..'z']) =>> oiPutStrLn produces a space leak, because the implementation isn't lazy enough, yet. 2) The OI-Comonad is a pointer to the current reality, together with the value, that can be extracted from OI. Whenever an OI ist rememberable by the user, the pointer will be duplicated. This is crucial for referential integrity. Comain, as defined by Andrew Bromage in : comain :: OI a -> () comain w = extract (w .>> show (a,b) =>> oiPutStrLn) where a = extract (w .>> () =>> oiGetChar) b = extract (w .>> () =>> oiGetChar) now works as intended and delivers, if 'x' is typed in on standard input: ('x','x') "a = ..." runs on reality w, yielding 'x' . "b = ..." is just a play back of "a = ...". "extract (w.>> show (a,b) =>> stdPutStrLn)" is another future of w, which just prints ('x','x'). module SimpleOI where import Control.Monad.Instances import System.IO.Unsafe import Data.Char import Data.IORef -------------------------------------- -- copied from http://www.eyrie.org/~zednenem/2004/hsce/ class Functor w => Comonad w where extract :: w a -> a duplicate :: w a -> w (w a) extend :: (w a -> b) -> (w a -> w b) extend f = fmap f . duplicate duplicate = extend id -- | 'fmap' defined in terms of 'extend' liftW :: Comonad w => (a -> b) -> (w a -> w b) liftW f = extend (f . extract) -- | 'extend' with the arguments swapped. Dual to '>>=' for monads. (=>>) :: Comonad w => w a -> (w a -> b) -> w b (=>>) = flip extend -- | Injects a value into the comonad. (.>>) :: Comonad w => w a -> b -> w b w .>> b = extend (\_ -> b) w -- end of copy ------------------------------------- data OIReality = OIReality GetChar [PutChar] Char data GetChar = GetChar Char OIReality data PutChar = PutChar () OIReality constructReality :: Char -> OIReality constructReality c = let r = OIReality (constructGet r) (constructPuts r) c in r constructGet :: OIReality -> GetChar constructGet r = let c = unsafePerformIO $ seq r getChar in GetChar c (constructReality c) constructPut :: OIReality -> Char -> PutChar constructPut r c = let v = unsafePerformIO $ seq r $ putChar c in PutChar v (constructReality c) constructPuts :: OIReality -> [PutChar] constructPuts r = map (constructPut r.chr) [0..255] nextGetCharReality :: OIReality -> OIReality nextGetCharReality (OIReality (GetChar c r) _ _) = r nextPutCharReality :: Char -> OIReality -> OIReality nextPutCharReality c (OIReality _ puts _) = let PutChar v r = puts !! (ord c) in seq v r data OIComonad a = OI (IORef OIReality) a -- extract OI _ a = a instance Functor OIComonad where fmap f (OI ref a) = seq a $ OI (unsafeDuplicateRef ref) (f a) -- too many seq's at the moment instance Comonad OIComonad where duplicate w = fmap (const w) w extract (OI _ a) = a mkOI :: Char -> OIComonad Char mkOI c = OI (unsafePerformIO $ newIORef $ constructReality c) c oiGetChar :: OIComonad a -> Char oiGetChar (OI ref _) = unsafePerformIO $ do { modifyIORef ref nextGetCharReality; OIReality _ _ c <- readIORef ref; return (c) } oiPutChar :: OIComonad Char -> () oiPutChar (OI ref c) = unsafePerformIO $ do { modifyIORef ref (nextPutCharReality c); OIReality _ _ d <- readIORef ref; -- not!? modified without further read return $ seq d ()} unsafeDuplicateRef :: IORef OIReality -> IORef OIReality unsafeDuplicateRef ref = unsafePerformIO $ do { r <- readIORef ref; newIORef r; } oiPutStrLn w = extract $ w =>> oiPutStr .>> '\n' =>> oiPutChar -- space leak if input string is suffiently long -- too many seqs in code oiPutStr w = extract $ oiPutStrS w .>> () oiPutStrS :: OIComonad String -> OIComonad String oiPutStrS w = case (extract w) of [] -> w (c:cs) -> oiPutStrS (w .>> c =>> oiPutChar .>> cs) oiGetLine = "t.b.d. using oiGetChar" -- adapted from http://www.mail-archive.com/haskell-cafe@haskell.org/ msg02408.html comain w = extract (w .>> show (a,b) =>> oiPutStr) where a = extract (w .>> () =>> oiGetChar) b = extract (w .>> () =>> oiGetChar) {- Original from http://www.mail-archive.com/haskell-cafe@haskell.org/ msg02408.html -- Bootstrap into the OI comonad main :: IO () main = return $! comain stdOI -- The following are the OI functions which we use. -- stdGetChar :: OI () -> Char -- stdPutStrLn :: OI String -> () comain :: OI a -> () comain w = coeval (w .>> show (a,b) =>> stdPutStrLn) where a = coeval (w .>> () =>> stdGetChar) b = coeval (w .>> () =>> stdGetChar) -}

3 3

Very Small Program
by Bernie Pope 03 Nov '06

03 Nov '06

On 02/11/2006, at 9:56 PM, ajb(a)spamcop.net wrote: > G'day all. > > Quoting Bernie Pope <bjpop(a)csse.unimelb.edu.au>: > >> This is a weird example of a pattern binding, and it is surprising >> (to me) that the syntax is valid. > > Maybe. But you wouldn't balk at this: > > numzeroes xs = sum [ 1 | 0 <- xs ] > > ...even if you wouldn't naturally express it that way. Patterns like > this are useful in places other than lets. I'd find it more > surprising > if lets were treated as a special case. > >> In this case you are defining the function which is bound to the >> variable called "+". > > Though thanks to n+k patterns, this is well-understood to be a > confusing and controversial case. > >> One would normally expect to see at least one variable inside the >> pattern on the >> left-hand-side of a pattern binding (otherwise what point would there >> be to the >> definition?). > > If the pattern is demanded (as it may well be in a list comprehension > generator, do block generator or a lambda), then it can be very > useful. > The programmer is asking for an error/empty list/monad "fail" if the > conformality check fails. I agree with what you say. When I said "pattern binding", I was using the terminology of the Haskell Report, which means only declarations of the form "pat = exp". Generator statements and lambdas are a different story, as you rightly point out. Nonetheless, I still believe that it is surprising for "pattern bindings" that this syntax is allowed, since there doesn't seem to be any purpose to them. (A cursory glance at the Report suggests that this kind of pattern binding is allowed). Then again, since the bindings are benign, maybe one could argue that it is better to have one less rule in the language definition? Then again, such a declaration could be the sign of a buggy program, and it might be better to give a compile time error. Cheers, Bernie.

1 0

Very Small Program
by Jason Dagit 03 Nov '06

03 Nov '06

Hello, I just found it (in ghci and hugs) that this is a valid haskell program: let 0 = 1 in 0 This program evaluates to 0 (to my surprise). I expected something similar to how this works: let { 1 + 1 = 3; 3 + 1 = 7 } in 1 + 1 + 1 Where you get 7. So, if the 0 is not used as an identifier (ie, defining a function or name of a value), then why doesn't this count as a parse error? And, why didn't I get to locally redefine it? Thanks, Jason

5 4

Fwd: [Haskell-cafe] Class
by Slavomir Kaslev 02 Nov '06

02 Nov '06

---------- Forwarded message ---------- From: Slavomir Kaslev <slavomir.kaslev(a)gmail.com> Date: Nov 2, 2006 10:47 AM Subject: Re: [Haskell-cafe] Class To: Daniel Fischer <daniel.is.fischer(a)web.de> On 11/2/06, Daniel Fischer <daniel.is.fischer(a)web.de> wrote: > Am Donnerstag, 2. November 2006 00:06 schrieb Slavomir Kaslev: > > Hello. > > > > I am new to Haskell and I am going through "Haskell: The craft of > > functional programming". I am trying to grasp haskell's classes and > > instances, so here is slightly modified code from the book: > > > > class Show a => Visible a where > > toString :: a -> String > > toString = show > > size :: a -> Int > > size = length . show > > > > instance Visible a => Visible [a] where > > toString = concat . map toString > > size = foldl (+) 0 . map size > > > > vSort :: (Visible a, Ord a) => [a] -> String > > vSort = toString . List.sort > ^^^^^^^ > my ghc complained that List.sort is not in scope, did you import Data.List as > List? Yes, I did imported Data.List. My mistake for forgetting to add it in the post. > > > > s = vSort [1..3] > > > > Unfortunetly in ghc it gives the following type error: > > Ambiguous type variable `a' in the constraints: > > `Visible a' arising from use of `vSort' at d:/tmp.hs:83:4-8 > > `Enum a' arising from the arithmetic sequence `1 .. 3' at > > d:/tmp.hs:83:10-15 > > `Num a' arising from the literal `3' at d:/tmp.hs:83:14 > > `Ord a' arising from use of `vSort' at d:/tmp.hs:83:4-8 > > Probable fix: add a type signature that fixes these type variable(s) > > Failed, modules loaded: none. > > > > As you can see, Visible is nothing more than an adapter to the Show > > class. How I got thing so far, [1..3] :: (Num a, Enum a) => [a], has a > > Show instance so does class Num (which 'subclasses' Show). Therefore, > > I can't see any reason why toString function can't call show from > > those instances. > > First problem: class Visible has no instances yet, so even if you disambiguate > the type by writing e.g. > s = vSort [1 :: Int .. 3], you'll get an error message: > Visible.hs:20:4: > No instance for (Visible Int) > arising from use of `vSort' at Visible.hs:20:4-8 > Probable fix: add an instance declaration for (Visible Int) > In the definition of `s': s = vSort ([1 :: Int .. 3]) Visible 'subclasses' Show. Doesn't this mean that Visible should be defined for all types with Show instances? I don't want to write Visible Int, if ghc has already defined a Show Int instance. > > And the second problem: > The typechecker has no means of determining which type 1 should have. > By virtue of the fact that numeric literals are overloaded in Haskell, it has > type Num a => a. The use of enumFromTo adds the Enum a constraint and vSort > adds Ord and Visible, however there may be many types satisfying these > constraints and ghc says it's up to you to select one. > And even if there is only one instance of Visible declared, ghc (nor, as far > as I know, any other Haskell implementation) won't select that because there > might, somewhere in a long-forgotten directory, lie a module dormant in which > another instance satisfying all constraints is declared. > To sum up: instance selection is left to the user, the compiler does only type > _inference_. Often that determines which instance fits, but sometimes you > have to give an expression type signature to tell the compiler what to > choose. I agree with second problem you pointed out. Thanks for mentioning it. -- Slavomir Kaslev -- Slavomir Kaslev

2 1

Class
by Slavomir Kaslev 02 Nov '06

02 Nov '06

Hello. I am new to Haskell and I am going through "Haskell: The craft of functional programming". I am trying to grasp haskell's classes and instances, so here is slightly modified code from the book: class Show a => Visible a where toString :: a -> String toString = show size :: a -> Int size = length . show instance Visible a => Visible [a] where toString = concat . map toString size = foldl (+) 0 . map size vSort :: (Visible a, Ord a) => [a] -> String vSort = toString . List.sort s = vSort [1..3] Unfortunetly in ghc it gives the following type error: Ambiguous type variable `a' in the constraints: `Visible a' arising from use of `vSort' at d:/tmp.hs:83:4-8 `Enum a' arising from the arithmetic sequence `1 .. 3' at d:/tmp.hs:83:10-15 `Num a' arising from the literal `3' at d:/tmp.hs:83:14 `Ord a' arising from use of `vSort' at d:/tmp.hs:83:4-8 Probable fix: add a type signature that fixes these type variable(s) Failed, modules loaded: none. As you can see, Visible is nothing more than an adapter to the Show class. How I got thing so far, [1..3] :: (Num a, Enum a) => [a], has a Show instance so does class Num (which 'subclasses' Show). Therefore, I can't see any reason why toString function can't call show from those instances. Can someone please enlighten my (still) C++ thinking head? -- Slavomir Kaslev

3 3

Basic Binary IO
by Nuno Pinto 02 Nov '06

02 Nov '06

Hi all! Today i was reading System.IO and didn't manage to understand how it works just by reading it. I looked the internet for some help on this, but only "advanced" information is available. Can anyone show me how to use openBinaryFile ? Just an example, like opening file "somefile" and separating it into something that can be edited in the code (like 8 bit words) then go to word nr12 and edit the last bit? Thanks! NP _________________________________________________________________ Search from any Web page with powerful protection. Get the FREE Windows Live Toolbar Today! http://www.toolbar.live.com

3 2

Re: [Haskell-cafe] What is the best way to preserve the order of a list (RESOLVED)
by John Ky 02 Nov '06

02 Nov '06

Thanks Stefan, -John On 11/1/06, Stefan Holdermans <stefan(a)cs.uu.nl> wrote: > > John, > > > My question is, how do I preserve the ordering of entities in my > > list and still be able to assign the proper order values to each > > entity? Is there an efficient way to do this? How else might I > > improve my orderByPriority algorithm. > > Straightforwardly, you could do it like this: > > import List (sortBy) > > type Priority = Int > type Order = Int > > order :: [Priority] -> [(Priority, Order)] > order = unlabel . sortOnLab . assignOrder . sortOnPrio . label > where > label = zip [0 ..] > unlabel = map snd > sortOnLab = sortBy (\(l, _) (m, _) -> compare l m) > sortOnPrio = sortBy (\(_, p) (_, q) -> compare p q) > assignOrder = \xs -> zipWith (\(l, p) o -> (l, (p, o))) xs [0 ..] > > For instance: > > > order [5, 2, 3, 7] > [(5,2),(2,0),(3,1),(7,3)] > > HTH, > > Stefan >

1 0

Post mesg
by Farida Mishra 02 Nov '06

02 Nov '06

Hi i would like to post mesg this list --------------------------------- Everyone is raving about the all-new Yahoo! Mail.

2 1

there's a monster in my Haskell!
by Andrew Pimlott 02 Nov '06

02 Nov '06

To boost the popularity of Scheme, Felleisen has argued for renaming "lambda" to "something cool, such as Funster".[1] Likewise, Haskell intimidates newcomers with the arcane term "monad". Peyton Jones's hopeful campaign to replace it with "warm fuzzy thing"[2] has so far produced few results. Inspired by Felleisen, and in the spirit of Halloween, I offer a new alternative: Meet "monsters", your computational companions in the land of lazy functional programming. To illustrate this proposal, I present here a gentle introduction to monsters. Monsters come in great variety, each type having its own special powers. But, as noted by Elmo[3], they are alike in an essential way. All monsters are capable of devouring values: devour :: Monster m => a -> m a The result of "devour x" is simply a monster that has ingested the value "x". Most monsters have a weakness and can be slain, liberating some ingested values or producing some other result. The instrument of demise varies, as do the possible outcomes, so this function is particular to a monster. If SomeMonster always yields a single value upon its demise, we would have slay :: SomeMonster a -> a The compassionate (and fastidious) programmer defers the gruesome (and messy) slaying while making use of the monster's special powers. But how to get at the monster's values short of that macabre act? Fortunately, monsters gladly contribute their values towards the creation of more monsters: (>>=) :: Monster m => m a -> (a -> m b) -> m b (>>=) should be read as the monster on the left expelling values through its rows of teeth and over its tongue at the function on the right. (Its pronunciation is a sort of bestial hissing that is difficult to describe; when you say it correctly, the terminal may become slightly moist.) Monsters range from the tame to the tumultuous, but we cannot let them run entirely amok. All therefore must obey the "monster laws". For instance, the regurgitation law states that immediately after devouring a value, a monster expels the same value: devour x >>= k === k x We have still seen none of the promised special powers. For that, we must look at a particular monster. The Either monster is defined as data Either a b = Trick a | Treat b This monster devours Treats, but if it doesn't get a Treat, it can play a Trick: playTrick :: t -> Trick t a playTrick t = Trick t This monster is commonly used as follows: takeFood :: Food -> Either Mischief Food takeFood Apple = playTrick eggHouse takeFood Raisins = playTrick tpTree takeFood CandyCorn = devour CandyCorn The divine among monsters is the mysterious and awesome IO. Its powers are vast, perhaps limitless, and beginners are taught that it cannot be slain. Like poisoned candy and release dates, this is of course a myth. The pure of spirit may, after meditation at the altar of referential transparency, cast the spell :: IO a -> a (When you are prepared to call this function, its name will be revealed.) The ST monster can be slain without esoteric ritual: slay :: (forall s. ST s a) -> a Yet philosophers whisper that there is something otherworldly about it, a kinship with IO. Eavesdropping on their debates, I hear the words "phantom type", but that gives me the chills so I leave them. [1] http://permalink.gmane.org/gmane.comp.lang.lightweight/3427 [2] http://research.microsoft.com/~simonpj/papers/haskell-retrospective/ [3] http://muppet.wikia.com/wiki/We%27re_All_Monsters

6 5

What is the best way to preserve the order of a list
by John Ky 02 Nov '06

02 Nov '06

Hi, I have a list of entities. Each entity has a priority field and an order field. The priority field contain the input values to my algorithm, the order fields contain the output value of my algorithm. My algorithm needs to assign 1 to the order field of the entity with the lowest priority value, 2 to the order field of the entity with the next lowest priority value, .... and so on. I've written a function orderByPriority that does that. However, it also does something else that is undesireable. It reorders the list. My question is, how do I preserve the ordering of entities in my list and still be able to assign the proper order values to each entity? Is there an efficient way to do this? How else might I improve my orderByPriority algorithm. Thanks -John > import Data.List > data Entity = Entity { > entityId :: Int, > priority :: Float, > order :: Int > } > initEntity = Entity { > entityId = 0, > priority = 0.0, > order = 0 > } > myList = [ > initEntity { entityId = 1, priority = 8.7 }, > initEntity { entityId = 2, priority = 5.4 }, > initEntity { entityId = 3, priority = 2.9 }, > initEntity { entityId = 4, priority = 5.4 }, > initEntity { entityId = 5, priority = 1.3 }, > initEntity { entityId = 6, priority = 3.5 }, > initEntity { entityId = 7, priority = 9.5 } > ] > comparePriority entity1 entity2 = > compare (priority entity1) (priority entity2) > orderByPriority :: [Entity] -> [Entity] > orderByPriority entities = assignOrder orderList 1 > where > orderList = sortBy comparePriority entities > assignOrder [] _ = [] > assignOrder (entity:entities) count = > (entity { order = count }):(assignOrder entities (count + 1)) > instance Show Entity where > show entity = "{" ++ > "entityId:" ++ (show $ entityId entity) ++ "," ++ > "priority:" ++ (show $ priority entity) ++ "," ++ > "order: " ++ (show $ order entity) ++ > "}"

4 4

class Defaults
by Bulat Ziganshin 02 Nov '06

02 Nov '06

Hello haskell-cafe, just one more nice snippet of code: class Defaults a where defaultValue :: a instance Defaults Bool where defaultValue = False instance Defaults [a] where defaultValue = [] instance Defaults (a->a) where defaultValue = id instance Num a => Defaults a where defaultValue = 0 class TestDefaultValue a where isDefaultValue :: a -> Bool instance TestDefaultValue Bool where isDefaultValue = not instance TestDefaultValue [a] where isDefaultValue = null instance Num a => TestDefaultValue a where isDefaultValue = (==0) -- This function is useful for defining default values, -- such as (directory ||| ".") or (memsize ||| 10*mb) a ||| b | isDefaultValue a = b | otherwise = a -- Useful for short-cutting boolean expressions, like this: -- putStr$ (need_separator &&& "\n\n") ++ (need_attention &&& map toUpper) str a &&& b | isDefaultValue a = defaultValue | otherwise = b -- |Apply function to value only if it is not empty unlessNull f xs = xs &&& f xs -- |Recursive list processing until list end, -- for example 'recursive (splitAt n)' splits list -- into the chuunks of n elements recursive :: ([a]->(b,[a])) -> [a] -> [b] recursive f list = list &&& (x:recursive f xs) where (x,xs) = f list -- |Split list into parts whose size defined by calling len_f -- at the yet unprocessed parts of list splitByLen :: ([a]->Int) -> [a] -> [[a]] splitByLen len_f = recursive (\xs -> splitAt (len_f xs) xs) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0

Simple GADT parser for the eval example
by Greg Buchholz 02 Nov '06

02 Nov '06

I'm trying to create a simple parser for the GADT evaluator from the wobbly types paper, and I need a little help. Here's the GADT and the evaluator... > data Term a where > Lit :: Int -> Term Int > Inc :: Term Int -> Term Int > IsZ :: Term Int -> Term Bool > If :: Term Bool -> Term a -> Term a -> Term a > Pair :: Term a -> Term b -> Term (a,b) > Fst :: Term (a,b) -> Term a > Snd :: Term (a,b) -> Term b > > eval :: Term a -> a > eval (Lit i) = i > eval (Inc t) = eval t + 1 > eval (IsZ t) = eval t == 0 > eval (If b t e) = if eval b then eval t else eval e > eval (Pair a b) = (eval a, eval b) > eval (Fst t) = fst (eval t) > eval (Snd t) = snd (eval t) > ...and instead of writing my own read instance, I thought I'd take a shortcut and just try converting a regular data type to our generalized one... > data Expr = ELit Int > | EInc Expr > | EIsZ Expr > | EPair Expr Expr > | EIf Expr Expr Expr > | EFst Expr > | ESnd Expr > deriving (Read,Show) > > my_read' :: Expr -> Term a > my_read' (ELit a) = Lit a > my_read' (EInc a) = Inc (my_read' a) > my_read' (EIsZ a) = IsZ (my_read' a) > my_read' (EPair a b) = Pair (my_read' a) (my_read' b) > my_read' (EIf p t e) = If (my_read' p) (my_read' t) (my_read' e) > my_read' (EFst a) = Fst (my_read' a) > my_read' (ESnd a) = Snd (my_read' a) ...That looks nice and simple, but it doesn't type check. GHCi-6.6 complains... Couldn't match expected type `a' (a rigid variable) against inferred type `Int' `a' is bound by the type signature for `my_read' at eval_gadt_wobbly.hs:45:24 Expected type: Term a Inferred type: Term Int In the expression: Lit a In the definition of `my_read': my_read (ELit a) = Lit a ...No surprise there, since there is no way to fail in the event of a maltyped "Expr". The next thing to try is a type class solution... > class MyRead a where > my_read :: Expr -> Term a > > instance MyRead Int where > my_read (ELit a) = Lit a > my_read (EInc a) = Inc (my_read a) > my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) > my_read (EFst a) = Fst (my_read a :: MyRead b => Term (Int,b)) > -- my_read (ESnd a) = Snd (my_read a) > instance MyRead Bool where > my_read (EIsZ a) = IsZ (my_read a) > my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) > -- my_read (EFst a) = Fst (my_read a) > -- my_read (ESnd a) = Snd (my_read a) > instance (MyRead a, MyRead b) => MyRead (a,b) where > my_read (EPair a b) = Pair (my_read a) (my_read b) > my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) > -- my_read (EFst a) = Fst (my_read a) > -- my_read (ESnd a) = Snd (my_read a) This just about works, except for the definitions for the "Fst" and "Snd" constructors. The compiler complains... Ambiguous type variable `b' in the constraint: `MyRead b' arising from use of `my_read' at eval_gadt_wobbly.hs:65:28-36 Probable fix: add a type signature that fixes these type variable(s) ...Of course, that makes perfect sense, since, if we're applying "Fst" to a term, then we don't care about the other branch of the "Pair". You can get it accepted by the type checker by making the types more concrete... my_read (EFst a) = Fst (my_read a :: Term (Int,Int)) ...or... my_read (EFst a) = Fst (my_read a :: Term (Int,Bool)) ...but how does a person fix this to work in the more general case? Or is this even the right way to build a parser for the GADT evaluator example? Notice the repetition needed: the "If", "Fst", and "Snd" defintions have to be copied to all three instances. Also, feel free to comment on this example, and the fact that it will evaluate with no problems. > static_vs_laziness = eval (my_read (EIf (EIsZ (ELit 0)) > (ELit 9) > (EIsZ (ELit 42)))::Term Int) Thanks, Greg Buchholz

7 9

hmake and ghc-6.6
by Alexey Rodriguez 02 Nov '06

02 Nov '06

Hello Haskell people, I have been trying to build hmake 3.12 using ghc-6.6 on a Fedora Core Linux running on a dual 64-bit Opteron machine. However, I had the following error related to the readline library: ---- /home/t-alexer/packages/hmake-3.12/script/hmake -hc=ghc HInteractive -d/home/t-alexer/packages/hmake-3.12/targets/x86_64-Linux/obj/interpreter \ -i../hmake -package util -package base -DUSE_READLINE=1 -lreadline -lncurses Warning: package(s) util not available (according to ghc-pkg) MkProg: Can't find module Readline in user directories . ../hmake Or in installed libraries/packages at /home/simonmar/fp/lib/x86_64-unknown-linux/ghc-6.6/imports /home/simonmar/fp/lib/x86_64-unknown-linux/ghc-6.6/imports Asked for by: SimpleLineEditor.hs Fix using the -I, -P, or -package flags. Stop - hmake dependency error. ---- I googled for this error and I saw the following thread in which Malcolm suggested having a fix. http://www.nabble.com/hmake-and-GHC-6.6-t2531880.html I tried to locate hmake's repository but to no avail. There is no link to it from www.haskell.org/hmake and the hmake in the nhc repository is the same as the hmake I downloaded. I will appreciate any help you can offer. Cheers, Alexey P.S. A related question, has any of you tried to build ghc using hat? I am trying to do this to study ghc's internals

2 2

An example of dependent types [was: Simple GADT parser for the eval example]
by oleg＠pobox.com 02 Nov '06

02 Nov '06

Greg Buchholz has posed an interesting problem of writing a typechecker. Given untyped terms of the form > data Expr = ELit Int > | EInc Expr > | EIsZ Expr .... we are to compute typed terms: > data Term a where > Lit :: Int -> Term Int > Inc :: Term Int -> Term Int > IsZ :: Term Int -> Term Bool That is, we need to write a function > typecheck :: Expr -> Term a Actually, Greg Buchholz posed a simpler example, of a function my_read > my_read :: Expr -> Term a Although it has the same signature, the intent is different. When the user writes "my_read exp", the user is supposed to *specify* the type of the desired result. Just as when we write "read 1", we are supposed to specify the type of the expected value: Int, Integer, etc. The function typecheck has a different intent: it *computes* the result type. It is indeed the typechecker: given the expression, we compute its type -- or report a failure if the expression is ill-typed. That is, the result *type* "Term a" is a function of the *value* Expr. Thus is truly a problem of dependent types. And Haskell is up to it: Haskell is genuinely a dependently typed language. We show the solution that uses no GADTs and no representation types. We retain however the eval function in the previous message that uses GADT. Our solution uses type classes. It seems to some the type-checking rules stated as instances of the TypeCheck class take a particular natural form. Indeed: > -- given term e, compute its type t > class TypeCheck e t | e -> t where > typecheck :: e -> Term t > instance TypeCheck FLit Int where > typecheck (FLit x) = Lit x > instance TypeCheck e Int => TypeCheck (FInc e) Int where > typecheck (FInc e) = Inc (typecheck e) > instance TypeCheck e Int => TypeCheck (FIsZ e) Bool where > typecheck (FIsZ e) = IsZ (typecheck e) > instance (TypeCheck e1 Bool, TypeCheck e2 t, TypeCheck e3 t) > => TypeCheck (FIf e1 e2 e3) t where > typecheck (FIf e1 e2 e3) = If (typecheck e1) (typecheck e2)(typecheck e3) > instance (TypeCheck e1 t1, TypeCheck e2 t2) > => TypeCheck (FPair e1 e2) (t1,t2) where > typecheck (FPair e1 e2) = Pair (typecheck e1) (typecheck e2) > instance TypeCheck e (t1,t2) => TypeCheck (FFst e) t1 where > typecheck (FFst e) = Fst (typecheck e) > instance TypeCheck e (t1,t2) => TypeCheck (FSnd e) t2 where > typecheck (FSnd e) = Snd (typecheck e) In the paper, the IsZ rule would have been written as |- e : int --------------- |- IsZ e : bool (We don't need the environment Gamma as our language has no variables). I submit the typeclass notation takes less space. The typechecking rules above operate on `lifted' terms: FLit, FInc, etc: > newtype FLit = FLit Int > newtype FInc e = FInc e > newtype FIsZ e = FIsZ e rather than the original terms Exp. The conversion is straightforward, via Template Haskell: > type F = Q TH.Exp > parse :: Expr -> F > parse (ELit x) = [e| FLit $(litE . integerL . fromIntegral $ x) |] > parse (EInc x) = [e| FInc $(parse x) |] > parse (EIsZ x) = [e| FIsZ $(parse x) |] The only inconvenience of using the Template Haskell is the necessity of splitting the whole code into two modules. we can then write: > e1 = "EIf (ELit 1) (ELit 2) (ELit 3)" > e2 = "(EIf (EIsZ (ELit 0)) " ++ > " (EInc (ELit 1)) " ++ > " (EFst (EPair (ELit 42) " ++ > " (ELit 43))))" > > t1' = $(parse . read $ e1) > t2' = $(parse . read $ e2) *G> :t t1' t1' :: FIf FLit FLit FLit *G> :t t2' t2' :: FIf (FIsZ FLit) (FInc FLit) (FFst (FPair FLit FLit)) > -- Causes the typechecking error: cannot match Int against the Bool > -- tt1 = typecheck t1' > tt2 = typecheck t2' *G> :t tt2 tt2 :: Term Int Obviously, e1 is ill-formed and so cannot be typechecked. The term e2 is well-typed, and the typechecker has figured out its type, which is Term Int. There was no need for any type annotation. The term tt2 can then be evaluated. The code: file GP.hs {-# OPTIONS -fglasgow-exts #-} module GP where import Language.Haskell.TH hiding (Exp) import qualified Language.Haskell.TH as TH (Exp) import Language.Haskell.TH.Ppr -- untyped terms, at Level 0 data Expr = ELit Int | EInc Expr | EIsZ Expr | EPair Expr Expr | EIf Expr Expr Expr | EFst Expr | ESnd Expr deriving (Read,Show) -- Untyped terms, at Level 1 type F = Q TH.Exp newtype FLit = FLit Int newtype FInc e = FInc e newtype FIsZ e = FIsZ e data FPair e1 e2 = FPair e1 e2 data FIf e1 e2 e3 = FIf e1 e2 e3 newtype FFst e = FFst e newtype FSnd e = FSnd e parse :: Expr -> F parse (ELit x) = [e| FLit $(litE . integerL . fromIntegral $ x) |] parse (EInc x) = [e| FInc $(parse x) |] parse (EIsZ x) = [e| FIsZ $(parse x) |] parse (EFst x) = [e| FFst $(parse x) |] parse (ESnd x) = [e| FSnd $(parse x) |] parse (EPair x y) = [e| FPair $(parse x) $(parse y) |] parse (EIf x y z) = [e| FIf $(parse x) $(parse y) $(parse z) |] show_code cde = runQ cde >>= putStrLn . pprint t0 = show_code . parse . read $ "EInc (EInc (ELit 1))" -- ill-typed expression e1 = "EIf (ELit 1) (ELit 2) (ELit 3)" e2 = "(EIf (EIsZ (ELit 0)) " ++ " (EInc (ELit 1)) " ++ " (EFst (EPair (ELit 42) " ++ " (ELit 43))))" t1 = show_code . parse . read $ e1 File g2.hs {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module G where import GP -- Typed terms data Term a where Lit :: Int -> Term Int Inc :: Term Int -> Term Int IsZ :: Term Int -> Term Bool If :: Term Bool -> Term a -> Term a -> Term a Pair :: Term a -> Term b -> Term (a,b) Fst :: Term (a,b) -> Term a Snd :: Term (a,b) -> Term b -- Typed evaluator [elided] -- Figure out the type of the expression e -- The type-checking rules are written in the natural notation [see the TypeCheck class and instances above. Elided to save space] t0' = $(parse . read $ "EInc (EInc (ELit 1))") t1' = $(parse . read $ e1) t2' = $(parse . read $ e2) tt0 = typecheck t0' -- Causes the typechecking error: cannot match Int against the Bool -- tt1 = typecheck t1' tt2 = typecheck t2' ttt0 = eval tt0 ttt2 = eval tt2

2 1

function types as instances of Num
by Greg Buchholz 01 Nov '06

01 Nov '06

Let's say we've got a little stack language, where you compute things by transformations of stacks, using compositions of functions from stacks to stacks (represented here as nested tuples). (See also Chris Okasaki's "Techniques for Embedding Postfix Languages in Haskell" www.eecs.harvard.edu/~nr/ cs252r/archive/chris-okasaki/hw02.ps ) For example, the simple program below calculates the square of 4... > {-# OPTIONS -fglasgow-exts #-} > > main = print $ test () > > test = square . (lit 4) > > lit :: Integer -> a -> (Integer,a) > lit val stack = (val, stack) > > dup (a, b) = (a, (a, b)) > mult (a, (b, c)) = (b*a, c) > square = mult . dup ...now let's say I find that using the function "lit" to annotation numeric literals ugly. What I really want is something like... > test' = square . 4 ...Seems simple enough, I'll just make an appropriate instance of Num and I'll be able to use fromInteger... > instance Eq (a -> (Integer, a)) > instance Show (a -> (Integer, a)) > instance Num (a -> (Integer, a)) where > fromInteger = lit ...but now when I try it, GHC complains... No instance for (Num (a -> (Integer, t))) arising from the literal `4' at final.hs:15:17 Possible fix: add an instance declaration for (Num (a -> (Integer, t))) In the second argument of `(.)', namely `4' In the expression: square . 4 In the definition of `test'': test' = square . 4 ...so it seems that (a -> (Integer, t)) can't be unified with (a -> (Integer, a)), or somesuch. Any thoughts on how to get this to work? Thanks, Greg Buchholz

4 5

More documentation: how to create a Haskell project
by dons＠cse.unsw.edu.au 01 Nov '06

01 Nov '06

There's been a bit of discussion on irc, lists and privately about about documenting publically the best practice for creating a new Haskell project -- be that a library or an application. Some advice is now available here: http://haskell.org/haskellwiki/How_to_write_a_Haskell_program Suggestions include: * use darcs * use cabal But we could do with more information on: * where to host a haskell project * integration of testsuites * anything about Hackage? * portability issues? So have a look at the page and make some suggestions, so it will be easier for newcomers in the future to create and contribute new projects, that will be readily accesible, useable and adopted by the community. -- Don

8 7

Accumulating related XML nodes using HXT
by Daniel McAllansmith 01 Nov '06

01 Nov '06

Hello. I have some html from which I want to extract records. Each record is represented within a number of <tr> nodes, and all records <tr> nodes are contained by the same parent node. The things I've tried so far end up giving me the cartesian product of record fields, so for the html fragment included below I'd end up with: [ Prod "Television" 17 "/prod17" "A very nice telly." , Prod "Television" 17 "/prod17" "Mind your fillings." , Prod "Cyclotron" 24 "/prod24" "A very nice telly." , Prod "Cyclotron" 24 "/prod24" "Mind your fillings." ] instead of: [ Prod "Television" 17 "/prod17" "A very nice telly." , Prod "Cyclotron" 24 "/prod24" "Mind your fillings." ] How should I go about accumulating related <tr> nodes into individual records? Thanks Daniel HTML fragment follows: ... <tr> <tr> <td>Product:</td> <td><a href="/prod17">Television</a> (code: 17)</td> </tr> <tr> <td>Description:</td> <td>A very nice telly.</td> </tr> <tr> <td><hr color="#00000"></td> </tr> <tr> <td>Product:</td> <td><a href="/prod24">Cyclotron</a> (code: 24)</td> </tr> <tr> <td>Description:</td> <td>Mind your fillings.</td> </tr> <tr> <td><hr color="#00000"></td> </tr> </tr> ...

2 3

hdbc linking errors
by Jeff Polakow 01 Nov '06

01 Nov '06

Hello, When trying to compile a standalone program using hdbc in cygwin, I get many linker errors. I have no problems using my code interactively with ghci. I am using the command line: ghc --make -package HDBC -package HDBC-odbc -O -o testExecute testExecute.hs Am I missing something? thanks Jeff -- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

1 1

Why is Haskell not homoiconic?
by Henning Sato von Rosen 31 Oct '06

31 Oct '06

Hi all! I am curious as to why Haskell not is homoiconic? I am interested in the reasons behind that design descision. I ask using this defintion og homiconicity: Homiconic means that "the primary representation of programs is also a data structure in a primitive type of the language itself" -- http://en.wikipedia.org/wiki/Homoiconic Examples: LISP, Rebol, Natural Languages... Thank you/Henning

4 3

Monad.Reader Licensing (Re: [Haskell] The Monad.Reader - Call for Copy)
by Conrad Parker 31 Oct '06

31 Oct '06

Hi, On Tue, Oct 31, 2006 at 12:10:21PM +0000, Wouter Swierstra wrote: > > * License: The entire magazine should be published under a > Creative Commons Attribution 2.5 License. This makes it much easier > to publish, distribute, teach, and share the Reader. This license > allows anyone to use the work in any way they seem fit as long as > credit is given to the original author. Given that articles written in LaTeX are likely to be written in literate Haskell (yay!), it's quite likely that their contents will be incorporated into software. Others have expressed misgivings about the use of the CC Attribution license for software. Usually the issue is that the method of attribution is unclear: the license leaves it up to the original author of each article to specify how they should be attributed (or not), and has some vague terms regarding "comparable authorship credit". A more detailed summary is at http://people.debian.org/~evan/ccsummary which suggests that such works would not be distributable by the Debian project. I suggest that articles in the Monad.Reader be BSD3 licensed, which has similar intent but clearer rules for incorporation in software. Besides, CC-BY-2.5 is not a member of Distribution.License in Cabal ;-) cheers, Conrad.

1 0

Tutorial: Writing a Lisp Interpreter In Haskell
by dons＠cse.unsw.edu.au 31 Oct '06

31 Oct '06

People might be interested in a new tutorial that's just appeared in blogspace, by coffeemug (of #haskell): http://www.defmacro.org/ramblings/lisp-in-haskell.html Also, its on reddit, http://programming.reddit.com/info/oj1w/details An enthusiastic view of the language from a newcomer's perspective. -- Don

2 1

Guidelines for proposing library changes
by dons＠cse.unsw.edu.au 31 Oct '06

31 Oct '06

After some discussion on the libraries list, I've put up the suggested 'best practice' for proposing library changes, here: http://haskell.org/haskellwiki/Library_submissions The idea is to reduce the number of 'bikeshed' discussions we're having, ensure that submissions are not dropped, and generally improve productivity. People should refer to this when proposing new functions for the core libraries, at risk of not having the suggestion adopted or considered ;) Cheers, Don

2 1

YAHT: searchAll5
by Magnus Therning 31 Oct '06

31 Oct '06

I can't get searchAll5[1] in Yet Another Haskell Tutorial to run. Ghci complains that it can't find a MonadPlus that satisfies the required type; it needs a MonadPlus. I suspect this is due to the use of 'mzero' and 'mplus', without making StateT a MonadPlus. My thought for this was to "push" mzero into the inner monad and have 'mplus' pass on to the inner monad: instance Monad m => MonadPlus (StateT state m) where mzero = StateT (\s -> return (s, mzero)) (StateT m1) `mplus` (StateT m2) = StateT (\s -> do (s1, a) <- m1 s (s2, b) <- m2 s1 return (s2, a `mplus` b)) What's above isn't accepted by ghci, and I don't even know for sure that my thought makes sense. /M [1]: http://en.wikibooks.org/wiki/Haskell/YAHT/Monads#Monad_Transformers -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus Software is not manufactured, it is something you write and publish. Keep Europe free from software patents, we do not want censorship by patent law on written works. Finagle's Fifth Law: Always draw your curves, then plot your readings.

2 1

Deriving class instances using DrIFT
by Daniel McAllansmith 31 Oct '06

31 Oct '06

Hi. I'm trying to derive some instances using DrIFT, but it will only work for me when I'm deriving for types in the current file or in the prelude. For example, this works: >module Test where > >{-! for Maybe derive : Haskell2Xml !-} this works: >module Test where > >data Foo = Foo > >{-! for Foo derive : Haskell2Xml !-} but this doesn't: >module Test where > >import Data.Word > >{-! for Word32 derive : Haskell2Xml !-} It fails to load the first import, giving an error as follows: {- Generated by DrIFT (Automatic class derivations for Haskell) -} {-# LINE 1 "Test.hs" #-} DrIFT: can't find module Data.Word Any ideas as to why that is? Thanks Daniel

3 4