January 2007 - Haskell-Cafe

Numeric Class Problem
by Dennis Buchmann 28 Jan '07

28 Jan '07

I've got a little problem i don't understand. I need to calculate an index for a list (by use of !!). It should look like this: floor(j * (n / p2n)) where j is an Integer, n is the length of a list, therefore Integer too, and p2n is 2^n. When i use the former line in my Haskell code (pasted at the end of this mail), i get the following error message: qc.lhs:464:16: No instance for (RealFrac Int) arising from use of `floor' at qc.lhs:464:16-36 Possible fix: add an instance declaration for (RealFrac Int) In the expression: floor (j * (n / p2n)) In the definition of `i': i = floor (j * (n / p2n)) In the definition of `genUf'': genUf' f j n | j == p2n = [] | otherwise = [(replicate (j + (y1 - y0)) 0) ++ ([1] ++ (replicate (p2n - ((j + (y1 - y0)) + 1)) 0))] ++ (genUf' f (j + 1) n) where y0 = mod j 2 y1 = xor y0 (f !! i) xor a b = mod (a + b) 2 p2n = (2 ^ n) i = floor (j * (n / p2n)) Failed, modules loaded: none. ------------------------------------------------------------------------ genUf :: [Int] -> QOp genUf f = (QOp(genUf' f 0 (length f))) where p2n = 2 ^ (length f) {- ok -} genUf' f j n | j == p2n = [] {- ok -} | otherwise = [(replicate (j+(y1-y0)) 0) ++ [1] ++ (replicate (p2n-(j+(y1-y0)+1)) 0)] ++ (genUf' f (j+1) n) where y0 = mod j 2 y1 = xor y0 (f!!i) xor a b = mod (a+b) 2 p2n = (2 ^ n) i = floor (j * (n / p2n))

3 2

Re: [Haskell-cafe] Glasgow Distributed Haskell
by Paul Johnson 28 Jan '07

28 Jan '07

Joel Reymont <joelr1(a)gmail.com> wrote: > I'm after Erlang in Haskell, if you will, for fault-tolerance and > scalability. I think the way to do Erlang in Haskell is to build a middleware layer on top of the language, not try to make the language into something it is not. In this kind of environment you need to be able to upgrade components while the system is running. The careful Haskell habit of separating stateful operations from pure functions is useful here. I gather that the HAppS project is working along similar lines, and for similar reasons. Take a look at it. http://happs.org/HAppS/README.html Paul.

2 1

Lazy ByteString Problem
by Dominic Steinitz 28 Jan '07

28 Jan '07

I've been playing around with streams as a way of implementing cryptographic functions as they seem to allow you to write code that reads more like the specification. However, I believe (and profiling seems to confirm this) that this builds up a large expression which only gets evaluated at the very end. I naively thought that using lazy bytestrings would solve the problem but the bytestring version just hangs even for small numbers. So two questions: 1. Are lazy bytestrings the answer but I am using them incorrectly? 2. What techniques are there to force evaluation and throw things that are no longer needed away? And can this be done without losing the spirit of the specification? Dominic. module Main(main) where import Data.Word import Data.Bits import Data.Char import System.Environment import qualified Data.ByteString.Lazy as BS -- ByteString version cbcl iv ps = ciphers where ciphers = 0xff `BS.cons` (BS.pack (BS.zipWith (+) feedIns ciphers)) feedIns = BS.pack (BS.zipWith xor (iv `BS.cons` ciphers) ps) -- Made up function to illustrate problem cbc iv ps = ciphers where ciphers = 0xff:(zipWith (+) feedIns ciphers) feedIns = zipWith xor (iv:ciphers) ps testl n = BS.last (cbcl 0x55 ((BS.pack . take n . repeat . fromIntegral . ord) 'a')) test :: Int -> Word8 test n = last (cbc 0x55 ((take n . repeat . fromIntegral . ord) 'a')) main = do progName <- getProgName args <- getArgs if length args /= 1 then putStrLn ("Usage: " ++ progName ++ " <length of string>") else (putStrLn . show . test . read) (args!!0)

1 1

Re: getting started with hsc (supercollider)
by Rohan Drape 27 Jan '07

27 Jan '07

Hello Alex, alex <alex(a)slab.org> writes: | Would anyone have some illustrative example code, and perhaps a | couple of tips for how to get things working well in emacs? Noting that Hsc is still experimental and not completely nailed down, though I think now quite close, and assuming that SuperCollider and ghc and emacs and the standard haskell emacs mode [1] are all installed and working, the following should get you started. * get hsc, or update if you have it (important, recent fixes required) darcs get http://slavepianos.org/rd/sw/sw-69 * compile it cd sw-69 runhaskell Setup.hs configure --prefix ~ runhaskell Setup.hs build runhaskell Setup.hs install --user (or there is a Makefile to do these three steps...) * add an appropriately modified variant of the following to ~/.emacs (push "/home/rohan/sw/sw-69/emacs" load-path) (setq hsc-interpreter "ghci") (setq hsc-help-directory "/home/rohan/sw/sw-69/Help/") (require 'hsc) * start the supercollider server scsynth -u 57110 That ought to be the end of premilinaries, this message is a 'literate SuperCollider Haskell file', save it with a .lhs extension, open it in emacs, make sure the Hsc menu comes up and read on. You can start ghci and load Sound.SC3 by typing C-cC-s (Hsc -> Haskell -> Start haskell). If the ghci output window becomes obscured you can see it again by typing C-cC-g (Hsc -> Haskell -> See output). The SuperCollider convention is that ordinary graph nodes are placed in a group with identifier 1, this node is not created when scsynth starts, so initially we will have to make it. The simplest way is to run the following line, and the simplest way to run a line is to put point on the line and type C-cC-c (Hsc -> Expression -> Run line). > withSC3 reset Doing this is so common there is a keybinding for it, C-cC-k (Hsc -> SCSynth -> Reset scsynth). To make a test sound run the following: > audition (sinOsc AR 440 0 * 0.1) This ought to play a quiet sine oscillator at A440. To see the server status type C-cC-w (Hsc -> SCSynth -> Display status). To stop the sound reset the server, ie. type C-cC-k. For expressions that don't fit on one line select the region and type C-cC-e (Hsc -> Expression -> Run region). This writes the region in a do block in a main procedure to a temporary file [2], loads the file and then runs main. > let f = sinOsc AR (xLine KR 1 1000 9 RemoveSynth) 0 * 200 + 800 > audition (sinOsc AR f 0 * 0.1) (To select a region use the mouse or place point at one end, type C-Space and move point to the other end.) To find help on a UGen or on a SuperCollider server command put point over the identifier and type C-cC-h (Hsc -> Help -> Hsc help). This opens the help file, which ought to have working examples in it, the above graph is in the sinOsc help file. To stop ghci type C-cC-x (Hsc -> Haskell -> Quit haskell). It may have been a mistake to just use .lhs as the extension, however it is not a disaster because the Hsc mode is a derivative of the haskell mode. Perhaps it ought to be changed to .hsc. Hope this is clear-ish, please send through any questions, bug reports or patches! Regards, Rohan [1] To get this loaded I have the following in ~/.emacs: (push "~/ext/src/haskell/fptools/fptools/CONTRIB/haskell-modes/emacs" load-path) (load "haskell-site-file.el") (add-hook 'haskell-mode-hook 'turn-on-haskell-doc-mode) (add-hook 'haskell-mode-hook 'turn-on-haskell-indent) (add-hook 'haskell-mode-hook 'turn-on-haskell-ghci))) [2] The file is written to /tmp/hsc.lhs, the preamble imports the following modules, this is enough to run the help file examples. import Sound.OpenSoundControl import Sound.SC3 import Control.Monad import System.Random

1 0

ANN: regex-tdfa 0.56
by Chris Kuklewicz 27 Jan '07

27 Jan '07

Greetings, My new regular expression backend "regex-tdfa" is passing all the tests I have been throwing at it, so it is time to share the good news. First up: Where is it? Version 0.56 is in my "stable" location at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-tdfa The version that will get updated and broken more often is "unstable" at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-unstable/regex-tdfa It needs a slightly updated regex-base package (version >= 0.80) at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-unstable/regex-base It has only been tested (on Max OS X) with GHC 6.6 and depends on base >= 2.0 for Data.ByteString, Data.ByteString.Lazy, and Data.Sequence. ** What does regex-tdfa do? It runs POSIX regular expression searches correctly. No other regular expression backend for Haskell does this correctly. The regular expression can be chosen to be from a String, ByteString, ByteString.Lazy, or (Data.Seq Char). Independent of that choice the searched text can also be any of those types. ** Properties and benefits of regex-tdfa: It follows a known standard: POSIX. (If you find that it disagrees with the standard then I will fix it.) It is written in Haskell, so there is no C library to compile and install. Though it is currently only written for GHC 6.6, it could be ported to any other compiler with only minor changes. (I expect that if you drop the polymorphic MPTC interface of regex-base it could be made Haskell98). It works with Unicode since it can be used on [Char] (and it works if there are '\NUL' characters around). It is lazy in the regular expression: it only builds the DFA if you use it, and only builds the state it needs, which are memoized in a lazy Trie. It is lazy in the searched text, and the pure function that searches the text only evaluates the text until the next match is done and does not hold onto the initial text. Thus you could efficiently search a [Char] up to the size of the Position type, which is an Int for now. It is free, the regex-tdfa library is under a BSD-3 license. ** Does it work? Yes. The regex-posix backend that come with GHC does not run all the searches correctly: it is buggy (example at end of announcement). And the regex-posix backend is also impossibly slow -- the slowest backend by far -- orders of magnitude slower. The regex-tre backend that wraps the TRE library has exposed this very fast library to the harsh gaze of QuickCheck. The lesson from QuickCheck is to never use regex-tre because the TRE library (version 0.7.4) is buggy. For regex-tdfa backend I took/stole ideas from Ville Laurikari's Master thesis which describes the algorithm that TRE uses. And I made a pure Haskell implementation that now passes all the tests at http://www.research.att.com/~gsf/testregex/testregex.html and follows the notes at http://www.research.att.com/~gsf/testregex/re-interpretation.html and passes those tests as well. And it "passes" QuickCheck tests which actually just compare the answers that regex-posix, regex-tre, and regex-tdfa since I do not have a bug free reference implementation to compare against. ** Why the name TDFA? Tagged Deterministic Finite Automata. The Tagged part is from Ville Laurikari's thesis work. ** Speed: If you do not care only about the match as a whole and not about subexpression matching then you can set the captureGroups ExecOption to False: makeMyRegex = makeRegex defaultCompOpt myExecOpt where myExecOpt = defaultExecOpt { captureGroups = False } And redefine (=~) and (=~~) to use makeMyRegex instead of makeRegex: (=~) :: (RegexMaker Regex CompOption ExecOption source,RegexContext Regex source1 target) => source1 -> source -> target (=~) s r = let re = makeMyRegex r :: Regex in match re s (=~~) :: (RegexMaker Regex CompOption ExecOption source,RegexContext Regex source1 target,Monad m)=> source1 -> source -> m target (=~~) s r = let re = makeMyRegex r :: Regex in match re s The benefit to this is speed, as it then proceeds to run all matches of "b(..?c)?d" against a large test file *faster* than the the TRE C library backend. My compliments to those who worked on ghc and -O2. It even runs nearly as fast as regex-dfa in this mode. Thus regex-dfa is (mostly) obsolete. If you use the default and capture the subgroups then the speed is reduced by a factor of about 4. This is because of the very simple data structures that keep track of the run time state. I intend to improve this aspect of the design now that I have a working algorithm. I have not benchmarked the speed of compiling the regular expression from the String. This compiling is done with very lazy data structures, so the DFA size is really only as big as you actually explore while running the match. ** Examples of bugs in regex-posix and regex-tre: An example for regex-posix: > *Main> "ab" Posix.=~ "((a)|(b)){2,}" :: MatchArray > array (0,3) [(0,(0,2)),(1,(1,1)),(2,(0,1)),(3,(1,1)) The array holds (group #, (match offset, match length)) The 0th group is the whole match "ab". The 2nd group is (a) and it matched the first "a" and the third group is (b) and matched the "b". But the second group is a child of the first group ((a)|(b)) which matched "b". The standard requires that captured groups are nested inside their parents, and here "a" is not not nested inside "b". So the regex-posix C backend that comes with GHC is buggy. The correct answer is, where the second group matched nothing: > *Main> "ab" TDFA.=~ "((a)|(b)){2,}" :: MatchArray > array (0,3) [(0,(0,2)),(1,(1,1)),(2,(-1,0)),(3,(1,1))] An example for regex-tre: "yyyyyy" TRE.=~ "(yyy|(x?)){2,4}" array (0,2) [(0,("yyyyyy",(0,6))),(1,("yyy",(3,3))),(2,("yyy",(3,3)))],"") Here TRE reports that the second group (x?) which should only match "" or "x" somehow matched "yyy". This is even more wrong than the regex-posix bug above. The correct answer, where the second group does not match: array (0,2) [(0,("yyyyyy",(0,6))),(1,("yyy",(3,3))),(2,("",(-1,0)))],"") -- Chris Kuklewicz

1 0

Trouble understanding records and existential types
by John Ky 27 Jan '07

27 Jan '07

Hi, A while back I asked about OO programming in Haskell and discovered existential types. I understood that existential types allowed me to write heterogeneous lists which seemed sufficient at the time. Now trying to combine those ideas with records: data AnyNode = forall a. Node a => AnyNode a class Node -- yadda yadda data Branch = Branch { name :: String, description :: String, children :: [AnyNode] } data Leaf = Leaf { name :: String, value :: String } The problem here is I can't use the same 'name' field for both Branch and Leaf. Ideally I'd like the name field in the Node class, but it doesn't seem that Haskell classes are for that sort of thing. -John

8 12

getting started with hsc (supercollider)
by alex 27 Jan '07

27 Jan '07

Hi all, I'm trying to get started on using Rohan Drape's Hsc library, excited about the prospect of parsing things straight into synthesis graphs, but progress is slow. There is good library documentation with examples, but no overview of how things fit together that I can find. Would anyone have some illustrative example code, and perhaps a couple of tips for how to get things working well in emacs? Once I get up to speed I would hope to contribute a beginner's guide back. Perhaps I should be addressing this email just to Rohan, but thought others might be able to help. alex

1 0

Type infer
by Marco Túlio Gontijo e Silva 27 Jan '07

27 Jan '07

Hello, I'm trying to define a partition__ function that is like Data.Set.partition, but use State Monad: > import Data.Set > import Control.Monad.State > partition__ f = > do > snapshot <- get > let > (firsts, rest) = Set.partition f snapshot > put rest > return firsts When I try to infer it's type in ghci I got: $ ghci ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. Prelude> :load partition.hs [1 of 1] Compiling Main ( partition.hs, interpreted ) Ok, modules loaded: Main. *Main> :type partition__ partition__ :: (MonadState (Set a) t, Ord a) => (a -> Bool) -> t (Set a) Ok, then I add > partition__ :: (MonadState (Set a) t, Ord a) => (a -> Bool) -> t (Set a) to the file and then: *Main> :reload [1 of 1] Compiling Main ( partition.hs, interpreted ) partition.hs:4:0: Non type-variable argument in the constraint: MonadState (Set a) t (Use -fglasgow-exts to permit this) In the type signature for `partition__': partition__ :: (MonadState (Set a) t, Ord a) => (a -> Bool) -> t (Set a) Failed, modules loaded: none. Why do I need glasgow-exts to specify a type infered by GHCi without -fglasgow-exts? Thanks. -- malebria Marco Túlio Gontijo e Silva Correio (MSN): malebria(a)riseup.net Jabber (GTalk): malebria(a)jabber.org Ekiga: malebria(a)ekiga.net IRC: malebria(a)irc.freenode.net malebria(a)irc.oftc.org Skype: marcotmarcot Telefone: 33346720 Celular: 98116720 Endereço: Rua Paula Cândido, 257/201 Gutierrez 30430-260 Belo Horizonte/MG Brasil

4 5

Concurrency in Haskell
by Alexy Khrabrov 26 Jan '07

26 Jan '07

What's the state of concurrency in Haskell? If Erlang's main strength is light-weight parallelism, can something like that be done in Haskell? Are there good examples of useful code employing GHC concurrency features one can play with? Cheers, Alexy

4 5

newbie timing question
by Sean McLaughlin 26 Jan '07

26 Jan '07

Hello, I'm trying to write a simple function to time an application. -- this doesn't work time f x = do n1 <- CPUTime.getCPUTime let res = f x in do n2 <- CPUTime.getCPUTime return (res,n2 - n1) On a function that takes 8 seconds to complete, returns (True,46000000) According to the documentation, this time is in picoseconds, making this 46 microseconds. I also tried -- neither does this time' f x = do n1 <- Time.getClockTime let res = f x in do n2 <- Time.getClockTime return (res,Time.diffClockTimes n2 n1) It returns something on that scale for picoseconds. How can I get a rough wall clock timing of functions? Thanks! Sean

4 3