- Haskell-Cafe - Haskell.org

Fwd: [Haskell-cafe] turning an imperative loop to Haskell
by Stephen Dolan 07 Sep '07

07 Sep '07

Sorry, forgot to cc list > I think this is called taking a good thing too far, but cool too: > > > f1 u = u + 1 > f2 u v = u + v > f3 u v w = u + v + w > > -- functions renamed for consistency) > zipWith1 = map > zipWith2 = zipWith > > -- and hey presto! > us1 = 3 : zipWith1 f1 us1 > us2 = 2 : 3 : zipWith2 f2 (drop 1 us2) us2 > us3 = 2 : 3 : 4 : zipWith3 f3 (drop 2 us3) (drop 1 us3) us3 How about this: import Data.List -- for transpose f = sum zipWithN fn = map fn . transpose us k = s where s = [2..k+1] ++ (zipWithN f $ x $ map (flip drop s) [0..k-1]) take 10 (us 1) [2,2,2,2,2,2,2,2,2,2] take 10 (us 2) [2,3,5,8,13,21,34,55,89,144] take 10 (us 3) [2,3,4,9,16,29,54,99,182,335] take 10 (us 4) [2,3,4,5,14,26,49,94,183,352] We can always take it further :D Stephen

1 0

Typeclasses and implicit parameters
by ajb＠spamcop.net 07 Sep '07

07 Sep '07

{-# OPTIONS -fglasgow-exts #-} -- G'day everyone. -- This is okay. f1 :: (?foo :: String) => String f1 = ?foo -- So is this. f2 :: (Show a, ?foo :: a) => a -> String f2 _ = show ?foo -- Hugs allows this. GHC rejects it on the grounds that "a" is unused -- on the right-hand side of the (=>). I think this is arguably a bug -- in GHC. f3 :: (Show a, ?foo :: a) => String f3 = show ?foo -- GHC rejects this. Hugs compiles it, but I can't call it as -- let ?foo = "Hello" in show Foo -- -- Is there a good reason to disallow this? data Foo = Foo instance (?foo :: String) => Show Foo where showsPrec _ Foo = showString ?foo . showString "Foo" -- Cheers, -- Andrew Bromage

4 5

ANNOUNCE: xmonad 0.3
by dons＠cse.unsw.edu.au 07 Sep '07

07 Sep '07

The xmonad dev team is pleased to announce the 0.3 release of xmonad. xmonad: a tiling window manager http://xmonad.org About: xmonad is a tiling window manager for X. Windows are arranged automatically to tile the screen without gaps or overlap, maximising screen use. All features of the window manager are accessible from the keyboard: a mouse is strictly optional. xmonad is written and extensible in Haskell. Custom layout algorithms, and other extensions, may be written by the user in config files. Layouts are applied dynamically, and different layouts may be used on each workspace. Xinerama is fully supported, allowing windows to be tiled on several screens. Features: * Very stable, fast, small and simple. * Automatic window tiling and management * First class keyboard support: a mouse is unnecessary * Full support for tiling windows on multi-head displays * Full support for floating windows * XRandR support to rotate, add or remove monitors * Per-workspace layout algorithms * Per-screens custom status bars * Easy, powerful customisation and reconfiguration * Large extension library * Extensive documentation and support for hacking Since xmonad 0.2, the following notable features and bug fixes have appeared: New features: * floating layer support: transients windows are not tiled by default, and windows may be dragged to and from a traditional floating layer (which allows mouse-resizing, and overlapping windows). * improved Xinerama support: workspace switching reuses multiple displays more effectively. * huge new extension library. Over 50 extensions to xmonad have been contributed by users, and are available all in a standard library, with documentation. More information, screenshots, documentation and community resources are available from: http://xmonad.org Xmonad is available from hackage, and via darcs. Happy hacking! The Xmonad Team: Spencer Janssen Don Stewart Jason Creighton Xmonad has also received contributions from at least: Alec Berryman Andrea Rossato Chris Mears Daniel Wagner David Glasser David Lazar David Roundy Hans Philipp Annen Joachim Fasting Joe Thornber Kai Grossjohann Karsten Schoelzel Michael Sloan Miikka Koskinen Neil Mitchell Nelson Elhage Nick Burlett Peter De Wachter Robert Marlow Sam Hughes Shachaf Ben-Kiki Shae Erisson Simon Peyton Jones Stefan O'Rear as well as many others on the IRC channel and mailing list. Thanks to everyone!

6 6

Speed of character reading in Haskell
by ok 07 Sep '07

07 Sep '07

I'm writing a tokeniser for a legacy programming language in Haskell. I started with the obvious main = getContents >>= print . tokenise where tokenise maps its way down a list of characters. This is very simple, very pleasant, and worked like a charm. However, the language has an INCLUDE directive, so I'm going to have to call readFile or something in the middle of tokenising, so the main tokeniser loop can't be a pure String -> [Token] function any more. It occurred to me to wonder whether it would be better to try to stick with the list of characters style as much as possible (and use readFile) or to switch over to character at a time processing (with openFile, hIsEOF, hGetChar, hClose). So I decided on an experiment: count the lines both ways. Method 1A (pure list processing) main = getContents >>= print . doit 0 doit n ('\n':cs) = doit (n+1) cs doit n ( _ :cs) = doit n cs doit n [] = n Method 1B (doit is in the IO monad) main = getContents >>= doit 0 doit n ('\n':cs) = doit (n+1) cs doit n ( _ :cs) = doit n cs doit n [] = print n Method 2 (character at a time) main = doit 0 doit n = isEOF >>= \eof -> if eof then print n else getChar >>= \c -> doit (if c == '\n' then n+1 else n) I tried this using GHC 6.4 on a 2.8 GHz PC running linux 2.6.20-1.2933.fc6 I don't know whether gcc was involved at all, but in case it was, the gcc version was 4.1.1. All test programs were compiled using ghc -o foobar -O foobar.hs The input was a 3.8 MB file. wc: 0.08 seconds total Method 1A: 0.30 seconds total Method 1B: 0.47 seconds total Method 2: ran out of stack Method 2': 2.21 seconds total. When I got the stack overflow, I suspected that this might be due to lazy evaluation of the integer argument to doit, so I changed the last line to doit $! (if c == '\n' then n+1 else n) and that worked. In *retrospect*, it is really obvious why this was necessary, but I must say that in *prospect* I wasn't expecting it. Other things being equal, I would have expected Method 2' to be faster. I'm now wondering if there is some other consequence of laziness that I am just not seeing. I'm also a little puzzled that there is a measurable difference between method 1A and method 1B. Things that I am not asking about: - ghc version; that's what's installed on the machine and if I want something different I may have to wait many days. - style comments on the list processing versions; yes I know how to write getContents >>= print . length . filter (=='\n') and that really has no relevance to the full tokeniser and in any case is slower than Method 1A.

1 0

wanted: HAppS example combining state and io
by Thomas Hartman 06 Sep '07

06 Sep '07

In the latest happs (darcs pulled, updated head is 0.9.1 iirc), I am experimenting with the example file in src/HAppS/Examples/HTTP1.hs. I would like to combine state with io. Eventually io will mean stuff like reading from a database, but for now I'm just reading a file. The example file HTTP1.hs has an example that demonstrates state with macid. I added an example that allows you to execute arbitrary io. I tried, but was unable to, add a handler that combines state and io. , h ["iohandler"] GET $ ioReadFileHandler , h ["statehandler"] GET $ stateHandler --, h ["ioandstatehandler"] GET $ ioAndStateHandler ..... -- displays contents of HAPPS.hs in current directory ioReadFileHandler = iohandler $ readFile "./HAppS.hs" -- displays incremented state counter stateHandler = ok $ \() () -> modify (+(1::Int)) >> get >>= respond . show -- should combine effect of iohandler with statehandler -- specifically, should display contents of HAppS.hs, and under that an incremented state handler -- is this possible ioAndStateHandler = undefined undefined Is mixing state and io possible with HAppS? If so, an example showing how to do it would be extremely helpful. best, thomas. --- 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.

2 2

let and fixed point operator
by Peter Hercek 06 Sep '07

06 Sep '07

Hi, I find the feature that the construct "let x = f x in expr" assigns fixed point of f to x annoying. The reason is that I can not simply chain mofifications a variable like e.g. this: f x = let x = x * scale in let x = x + transform in g x When one is lucky then it results in a compile error; in worse cases it results in stack overflow in runtime. The annoying part is figuring out new and new variable names for essentially the same thing to avoid the search/evaluation of the fixed point. I suppose Haskell was designed so that it makes sense. The only usage I can see is like this: let fact = \x -> if x == 0 then 1 else x * fact (x-1) in ... but that is not any shorter than: let fact x = if x == 0 then 1 else x * fact (x-1) in So the question is what am I missing? Any nice use cases where fixed point search is so good that it is worth the trouble with figuring out new and new variable names for essentially the same stuff? Peter.

30 66

Re: [Haskell] (no subject)
by Scott Williams 06 Sep '07

06 Sep '07

[bcc haskell, cc haskell-cafe] On 9/5/07, Tomi Owens <t.owens(a)hautlieu.sch.je> wrote: > > Hi there. I'm a teacher of Maths and am working my way through the Euler > Project problems for fun. I have mostly been using Basic, but have read up > about Haskell and think it looks like a sensible way to solve many of the > problems. > > OK, so I've downloaded GHCi and am trying to teach myself. > > So far I have done this: > > ___ ___ _ > / _ \ /\ /\/ __(_) > / /_\// /_/ / / | | GHC Interactive, version 6.6.1, for Haskell 98. > / /_\\/ __ / /___| | http://www.haskell.org/ghc/ > \____/\/ /_/\____/|_| Type :? for help. > > Loading package base ... linking ... done. > Prelude> let f (a,b) = a * floor (100000/b) > Prelude> f(2,5) > 40000 Here you can find out type ghci has inferred for this function. > :t f f :: (RealFrac b, Integral b1) => (b1, b) -> b1 This function works just as I want it to. > > Now I try creating a list: > > Prelude> [(a2+b2,a)| a <- [1..4] , b<- [1..4], a2+b2<20, b<=a] > [(2,1),(5,2),(8,2),(10,3),(13,3),(18,3),(17,4)] Let's assign this to an intermediate variable so we can query it's type: Prelude> let lst = [(a ^ 2 + b ^ 2, a) | a <- [1..4], b <- [1..4], a^2 + b^2 < 20, b <= a] Prelude> lst [(2,1),(5,2),(8,2),(10,3),(13,3),(18,3),(17,4)] Prelude> :t lst lst :: [(Integer, Integer)] aha; here's the source of the type mismatch: Prelude> :t floor floor :: (RealFrac a, Integral b) => a -> b Floor has to take a RealFrac. According to hoogle[1], we can use various floating-point approximations (Float, Double, CFloat, etc) or we can use the exact Rational type. [1] http://haskell.org/hoogle/?q=RealFrac You can get your types to match by declaring your list to be of type [(Rational, Rational)] either by explicitly typing one of the untyped variables or the entire expression: Prelude> let lst = [(a ^ 2 + b ^ 2, a) | (a::Rational) <- [1..4], b <- [1..4], a^2 + b^2 < 20, b <= a] Prelude> :t lst lst :: [(Rational, Rational)] Prelude> let lst :: [(Rational, Rational)] = [(a ^ 2 + b ^ 2, a) | a <- [1..4], b <- [1..4], a^2 + b^2 < 20, b <= a] Prelude> :t lst lst :: [(Rational, Rational)] and this works > So now I try to apply the function to the list: > > Prelude> map (f) [(a2+b2,a)| a <- [1..4] , b<- [1..4], a2+b2<20, b<=a] > > and I get this result: > > <interactive>:1:5: > Ambiguous type variable `t' in the constraints: > `Integral t' arising from use of `f' at <interactive>:1:5 > `RealFrac t' arising from use of `f' at <interactive>:1:5 > Probable fix: add a type signature that fixes these type variable(s) I'm sorry, but I don't quite get how to set the type signature and how it > will apply to my function... > > Thanks, Hope this helps Tomi > -------------------------------------------------------------------------------- > > > Department for Education, Sport and Culture E Mail > This message is for the named person's use only. It may contain > confidential, proprietary or legally privileged information. No > confidentiality or privilege is waived or lost by any mistransmission. > If you receive this message in error, please immediately delete it and all > copies of it from your system, destroy any hard copies of it and notify the > sender. You must not, directly or indirectly, use, disclose, distribute, > print, or copy any part of this message if you are not the intended > recipient. The Department for Education, Sport and Culture and any of its > establishments each reserve the right to monitor all e-mail communications > through its networks. > > Any views expressed in this message are those of the individual sender, > except where the message states otherwise and the sender is authorised to > state them to be the views of any such entity. > > The Department for Education, Sport and Culture shall not be liable to > the recipient or any third party for any loss or damage, however it appears, > from this e-mail or its content. This includes loss or damage caused by > viruses. It is the responsibility of the recipient to ensure that the > opening of this message and its attachments shall not adversely affect > systems or data. > > > -------------------------------------------------------------------------------- > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > > -- Scott Williams

3 3

Code from "Why Functional Programming Matters"
by Andrew Wagner 06 Sep '07

06 Sep '07

I've been reading the classic "Why functional programming matters" paper [1] lately, particularly looking at the alpha beta stuff. I've ported all his code to haskell, but I have a question. His algorithm takes a board position, creates a gametree out of it, maps a static evaluation function over the gametree, then uses alpha beta to find the real evaluation from a Tree Int. But of course, in an actual application, what you actually want is the best MOVE from the current position (or, even more ideally, the so-called "principal variation", which is the best series of moves from the current position). Is there a good way to collect this, without mapping some sort of function over the tree that puts a list of moves on every node too? Hughes seems to completely ignore this, and I wonder if it's because it gets ugly to implement.

9 12

Re: [Haskell-cafe] Re: [Off topic] Proving an impossibility
by Miguel Mitrofanov 05 Sep '07

05 Sep '07

> It depends on arbitrary restrictions on what constitutes an > (boolean) expression, something that is anathema to > functional programmers :-) Spot the language: > while if E > then S; F > else False > fi > do T > od > > It reminds me of a paper by Knuth, where he states that > > "goto" statement is necessary; don't remember the title, > > however. > I don't remember needing a goto in Haskell... Well, for imperative languages, of course.

6 7

[Off topic] Proving an impossibility
by Vimal 05 Sep '07

05 Sep '07

Hi In my Paradigms of Programming course, my professor presents this piece of code: while E do S if F then break end T end He then asked us to *prove* that the above programming fragment cannot be implemented just using if and while statement, even if S and T can be duplicated a finite number of times He also asked us to state our assumptions if any. 1. We have assignment statements (to create a flag and check) 2. The execution of E or F does not affect execution of S or T... Well, learning Haskell, I quickly realized that even if S and T have to be expressions and came up with this, assuming that 1. There are boolean operations 2. Boolean expressions are evaluated from Left to Right 3. Boolean expressions can be short-circuited while E and (S or 1) and F and (T or 1) do (* Nothing *) end But I would also like to consider an option of proving that its impossible, under the given constraints... Any thoughts? Vimal

4 3