October 2006 - Haskell-Cafe

Separate a string into a list of strings
by Sara Kenedy 18 Apr '08

18 Apr '08

Hi all, I want to write a function to separate a string into a list of strings separated by commas. Example: separate :: String -> [String] separate "Haskell, Haskell, and Haskell" = ["Haskell", "Haskell", "and Haskell"] If anyone has some ideas, please share with me. Thanks. S.

14 35

Creating static libraries using GHC
by Tom Hawkins 16 Mar '07

16 Mar '07

I have a chunk of Haskell code I would like wrap up and distribute as a library. Is there a way to build a static library (*.a) that includes my code plus the Haskell runtime, which C programs can easily link against? Here is what I have tried so far... ghc --make -fffi MyLib # Builds MyLib.o and MyLib_stub.o. gcc -c -I/usr/local/lib/ghc-6.4.1/include MyLibWrapper.c ar -r libMyLib.a MyLib.o MyLib_stub.o MyLibWrapper.o This works fine when I use ghc to compile and link a C program... ghc main.c libMyLib.a But if I use gcc, it throws a lot of unresolved references. I have no problem compiling with ghc, but the folks using my library probably won't have it installed. I added -v to ghc to see how it calls gcc; it seems to link in different libraries based on what Haskell libraries are being used, and it undefines a bunch is symbol references. Are there any switches to have ghc return a single archive with everything included? Please excuse my ignorance of the linking process. Thanks for any help! -Tom

3 2

Are associated types synonyms like type classes?
by Brian Smith 17 Nov '06

17 Nov '06

I read the easy parts of the "Associated Types with Class" and "Associated Type Synonyms" papers. An associated type synonym seems to kind of work similarly to a restricted form of class. In what way are the two following examples different? -- define a class with a type synonym, and a set of operations class A a where type B b foo :: a -> B b instance A Int where type B = Bool foo = (==0) -- define two classes, and an function that . class A a, B b where foo :: a -> b instance A Int, B Bool where foo = (==0) Also, has anybody written a paper on the differences between typeclasses + associated types and ML's module system + overloading? Thanks, Brian

4 5

forall and a parse error
by Neil Mitchell 15 Nov '06

15 Nov '06

Hi, I was experimenting with forall and higher rank types briefly, in particular: x :: [forall a . a] This is illegal because of: http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.htm… Which is fine, however its surprising to compare the error messages: [forall a . a] parse error on input `forall' [(forall a . a)] Illegal polymorphic or qualified type: forall a. a In the type signature: lst :: [(forall a. a)] In normal Haskell, I tend to view [x] as equivalent to [(x)] (provided that x is not a tuple) but in this case it has a different meaning - albeit both are erronous meanings. When running the example with Hugs, they both come out as syntax errors - the first on the forall, the second on the closing square bracket. Thanks Neil

5 6

submenu doesn't seem to work properly in wxhaskell
by Maarten 15 Nov '06

15 Nov '06

Dear all, The following code doesn't seem to work properly. Either the main entry (m1/mp1) or it's sub menu entry (ms1/mps1) do not seem to propagate the event when pressed. It is possible to make it working by uncomments the lines where the menu commands are registered in the frame. I have the following two questions: 1. Why doesn't the plain code work. Am I missing something or doing something wrong? 2. Doesn't registering eventhandlers in the frame introduce a memory/resource leak, especially in the case of popups? Any suggestions or comments appreciated. Thanks. Kind regards, Maarten Code: <imports> gui :: IO () gui = do f <- frame [ text := "Hello world!" ] m <- menuPane [ text := "&Menu" ] m1 <- menuItem m [ text := "Menu m1", on command := putStrLn "menu m1"] -- set f [ on (menu m1) := putStrLn "menu m1" ] menuLine m sub <- menuPane [text := "Sub menu"] ms1 <- menuItem sub [ text := "submenu ms1", on command := putStrLn "submenu ms1" ] -- set f [ on (menu ms1) := putStrLn "submenu ms1" ] menuSub m sub [ text := "Sub" ] menuItem m [text := "E&xit", on command := close f] set f [menuBar := [m], on mouse := mouseEvent f, clientSize := sz 200 200 ] return () mouseEvent f eventMouse = do case eventMouse of MouseRightDown mousePoint _ -> doPopup f mousePoint _ -> return () doPopup f mousePoint = do m <- makePopupMenu f "&Popup" "Doesnt' work..." menuPopup m mousePoint f objectDelete m makePopupMenu f c t = do mp <- menuPane [ text := c ] mp1 <- menuItem mp [ text := "Popup mp1", on command := putStrLn "popup mp1"] -- set f [ on (menu mp1) := putStrLn "popup mp1" ] menuLine mp sub <- menuPane [text := "more text"] mps1 <- menuItem sub [ text := "Popup mps1", on command := putStrLn "popup mps1"] menuSub mp sub [ text := "Sub" ] -- set f [ on (menu mps1) := putStrLn "popup mps1" ] return mp

2 2

deepSeq vs rnf
by Chad Scherrer 14 Nov '06

14 Nov '06

Hi, I had posted this question a while back, but I think it was in the middle of another discussion, and I never did get a reply. Do we really need both Control.Parallel.Strategies.rnf and deepSeq? Should we not always have x `deepSeq` y == rnf x `seq` y ? Maybe there's a distinction I'm missing, but it seems to me they're basically the same. -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

5 5

A type class puzzle
by Yitzchak Gale 12 Nov '06

12 Nov '06

Consider the following sequence of functions that replace a single element in an n-dimensional list: replace0 :: a -> a -> a replace0 = const replace1 :: Int -> a -> [a] -> [a] replace1 i0 x xs | null t = h | otherwise = h ++ (replace0 x (head t) : tail t) where (h, t) = splitAt i0 xs replace2 :: Int -> Int -> a -> [[a]] -> [[a]] replace2 i0 i1 x xs | null t = h | otherwise = h ++ (replace1 i1 x (head t) : tail t) where (h, t) = splitAt i0 xs etc. Generalize this using type classes.

8 14

Automatic fixity allocation for symbolic operators
by Brian Hulley 11 Nov '06

11 Nov '06

Hi - I'm wondering if it is possible to construct a methodical procedure to assign a fixity to symbolic operators so that we could get rid of the need for user defined fixites. User defined fixities are an enormous problem for an interactive editor, because it is not possible to construct a parse tree of some code if you don't know what the fixities are, and an editor must be able to do something useful with a code fragment without having to look inside other modules (because the other modules may not yet have even been written!). Also, the programmer or reader of code needs to be able to understand each code fragment independently as well. >From the Haskell98 report, the Prelude defines: infixr 9 ., !! infixr 8 ^, ^^, ** infixl 7 *, /, `quot`, `rem`, `div`, `mod` infixl 6 +, - infixr 5 :, ++ infix 4 ==, /=, <, <=, >=, > infixr 3 && infixr 2 || infixl 1 >>, >>= infixr 1 =<< infixr 0 $, $!, `seq` Suppose we ignore the varid operators and just consider the symbolic ops. What I'm trying to find is a systematic way to assign fixities to all other possible sequences of symbol characters that is consistent with what we've already got in the Prelude. As a first step, we could say that "mirrored" operators must share the same precedence ie: =<< >>= < > For associativity, we could assign each character an associativity weight: -1 left associative 0 neutral 1 right associative and say that the associativity is simply the sign of the sum of the associativity weights of the characters thus: > -1 = 0 < 1 =<< 0 + 1 + 1 ie infixr Note that I don't care about non-associative ops since the non-associativity of something should be a question for the type checker not the parser imho - ideally we should be able to create a parse tree for any possible operator expression. To form the precedence, we could assign each character a precedence value eg: 9 . ! 8 ^ 7 * / 6 + - 5 : 4 = 3 & 2 | 1 < > 0 $ A first attempt might be to say that the precedence is simply the decimal expansion of the precedence values eg >>= has precedence 1.14 and $! has precedence 0.9. However, as noted above, mirrored ops must share the same precedence so an alternative is to create some ordering of characters such that when the set of characters in an operator is sorted according to this ordering, the decimal expansion of the precedence digits will give the same relative ordering for operator precedences as the Prelude. For example, using $ | & + - * / ^ . ! : < > = as the ordering, we'd get: infixr 9 . !! 9 9.9 infixr 8 ^, ^^, ** 8 8.8 7.7 infixl 7 *, /, 7 7 infixl 6 +, - 6 6 infixr 5 : , ++ 5 6.6 infix 4 ==, /=, <, <=, >=, > 4.4 7.4 1 1.4 1.4 1 infixr 3 && 3.3 infixr 2 || 2.2 infixl 1 >>, >>= 1.1 1.14 infixr 1 =<< 1.14 infixr 0 $, $! 0 0.9 Although most existing ops get a similar precedence (eg ^ ^^ and ** are all still in the same group relative to the other ops despite the fact that within the group there is now an ordering) the main problem seems to be that < <= >= > get precedences that bind too loosely and /= is totally wrong. This problem aside, the above algorithm would give sensible precedences for such things as: :> <: 5.1 <+> <*> 6.11 6.11 where the use of <> neutralizes the associativity contribution of < or > respectively (since (-1) + 1 == 0), giving us the intuitive associativity we'd expect from the "interesting" character in the middle. (The problem of /= getting 7.4 could be solved by putting / after = in the order, to get 4.7, but unfortunately this would mean that since <> must be before =, <> would be before / so </> would get the wrong precedence compared to <*>) Another issue is that there is no assignment of associativity weights such that "*" is infixl but "**" is infixr (ditto + and ++) so perhaps we'd need to associate each character with an associativity function. Similar to precedences, we then define an associativity ordering and let the resulting associativity be the sign of the composition of the sorted functions applied to 1 eg: ^ const (-1) * \x -> x * (-1) = id & const (-1) < (+1) > (+ (-1)) Then * (\x -> x * (-1)) 1 === -1 ie left ** (\x -> x * (-1)) . (\x -> x * (-1)) $ 1 === +1 ie right >>= > > = (+ (-1)) . (+ (-1)) . id $ 1 === -1 <*> -- remember ordering * < > (\x -> x * (-1)) . (+1) . (+ (-1)) $ 1 === ((1 - 1) + 1) * (-1) === -1 ie left as required!!! :-) Anyway this is as far as I've got so far trying to rationally reconstruct the original Prelude precedences to achieve the golden aim of eliminating the infinite problem of fixity declarations from source code... :-) (Regarding `div` `seq` etc - I'd just assign them all the same precedence because use of multiple varid ops in the same expression with different precedences, or trying to combine them with symbolic ops, is just a highway to confusion city imho. Note also that (seq x $ exp) is not only clearer but is also one character shorter than (x `seq` exp)) The main open problem is finding an algorithm which assigns a good precedence to >>= as well as to >= and /= and </> and <*>.... ;-) Any ideas? Thanks, Brian. -- www.metamilk.com

21 57

Announcement: new maintainers forr wxHaskell
by Jeremy O'Donoghue 11 Nov '06

11 Nov '06

Hi all, I'd like to announce that we have a new team of maintainers in place for wxHaskell, so we're hoping that this list will see a significant increase in activtiy in the future. We have several near-term objectives, which will likely occur in roughly the order below: * Pull together all of the patches for various wxHaskell functionalities which are 'out there' into the core distribution. * Enhance support for Unicode. * Ensure that we support GHC 6.4.2 and GHC 6.6. * Add support for wxWidgets 2.6.3 and maintain support for wxWidgets 2.4.2. There are very good reasons why many wxHaskell users will want to continue to use 2.4.2. * 'Cabalize' the wxHaskell build system. * Add new examples and increase the coverage of different wxWidgets functionalities. * Create binary releases / installable packages for popular platforms (Windows, Mac, Debian are current favourites) The maintainers will work mainly on a public Darcs repository at http://darcs.haskell.org/wxhaskell, which will always contain the latest patches, but which may not always be stable. I will, from time to time, release reasonably stable updates of files to Sourceforge CVS, and we will aim for binary releases whenever this makes sense. I'd ask the community to send patches via this list. They will get added to the public Darcs repository once at least one of the maintainers has successfully integrated and built them. We will create a separate developers list if the volume of patches ever threatens to overwhelm the wxhaskell-users list :-) To go with the above, I hereby provide first patch to to the archive at http://darcs.haskell.org/wxhaskell as an attachment. This patch brings together patches from a number of sources (mainly Shelarcy and Eric) to provide some support for Unicode variants of wxWidgets, a couple of extra widgets, preliminary support for wxWidgets 2.6.3 and a patch to enable build with GHC 6.6. None of this would have been possible without a great bunch of volunteers who have come forward and shown great patience with the slow pace at which I have pulled this together. Eric Kow, Shelarcy, Mads Lindstrøm, Time Docker and Frank Berthold have all offered their assistance, and should take a virtual bow. Finally, none of this would have been possible without the assistance of Daan Leijen, the original author of most of wxHaskell, who has been gracious enough to offer advice, and to pass on everything we need to move forward.

4 3

Permutation with k levels
by Nuno Pinto 07 Nov '06

07 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