November 2006 - Haskell-Cafe

How to design default implementations of type class methods?
by Henning Thielemann 08 Nov '06

08 Nov '06

I like to hear some opinions about how to implement class method defaults. Let's consider the following example: I want to classify types which allow for computation of the greatest common divisor. The greatest common divisor can be computed by Euclid's algorithm in some cases (integers, univariate polynomials) but not in all cases (integer matrices, multivariate polynomials). So maybe it's a good idea to set the Euclidean algorithm as default implementation for the GCD method. Say, I have already implemented both the normal Euclidean algorithm as "euclid", which only emits the GCD, and the extended Euclidean algorithm "extendedEuclid" which also determines a and b in "gcd(x,y) = a*x + b*y" for given x and y. Now I have two choices for implementing default methods: 1. Implement a method by calling other methods of the same class. class (Units a) => PID a where extendedGCD :: a -> a -> (a,a,a) extendedGCD = extendedEuclid divMod gcd :: a -> a -> a gcd x y = let (g,_,_) = extendedGCD x y in g Advantage: User must implement only few methods, here extendedGCD, the other ones work automatically. Disadvantage: User must know, how the default methods call each other, in order to not introduce cycles. 2. Implement a method by calling custom code, preferably a public function according to http://www.haskell.org/haskellwiki/Slim_instance_declaration class (Units a) => PID a where extendedGCD :: a -> a -> (a,a,a) extendedGCD = extendedEuclid divMod gcd :: a -> a -> a gcd = euclid mod Advantages/Disadvantages are negated with respect to the first item. :-) Ok, this example class is not well chosen, because in the case of multivariate polynomials, not only extended Euclidean algorithm fails, but it is in many cases not possible to represent the GCD of x and y as a linear combination of x and y. My question is not limited to this case: I want to know, what reasons exist pro and cons each alternative. Currently I prefer the first way, because it reduces the work of implementing instances to the things that are essential for the particular type. People who want specialized and more efficient methods, must implement all methods.

3 2

Re: ANN: System.FilePath 0.10
by Ashley Yakeley 08 Nov '06

08 Nov '06

Neil Mitchell wrote: > 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. How do I manipulate a Windows file path on a POSIX machine (something relating to Samba, for instance)? -- Ashley Yakeley

2 1

Re: Fractional/negative fixity?
by Robert Dockins 08 Nov '06

08 Nov '06

On Nov 8, 2006, at 3:58 AM, apfelmus(a)quantentunnel.de wrote: > Lennart Augustsson wrote: >> >> 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 >> [...] >>> >>> 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. :) > > Actually, that's one of the use cases ;) A turing-complete type-checker isn't enough! Our work is not complete until the parser is a universal machine as well! > Regards, > apfelmus Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

1 0

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 07 Nov '06

07 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 07 Nov '06

07 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 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

Efficiency of bang patterns
by Chad Scherrer 07 Nov '06

07 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