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

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

06 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