- Haskell-Cafe - Haskell.org

saner shootout programs
by J C 15 May '08

15 May '08

I don't know Haskell very well, but even I can tell, looking at, for example, the N-body benchmark, that the Haskell code is probably not type-safe, and the tricks used in it would not be usable in a larger program (see below). The task is essentially a pure computation: take a list of bodies having mass, position and velocity; apply Newton laws at discrete intervals for a large number of times; return new positions and velocities. I could write a C++ procedure that performs this task and have some piece of mind regarding its type correctness, exception safety and functional purity: side effects would be local to the procedure, arguments passed as const or by value, the result returned by value, no type casts or new/delete operators used. On the other hand, the Haskell code makes assumptions about the size of double-precision floats (obviously not type-safe). Further, the simulation is not a pure function. It is often argued that one only needs these dirty tricks in the most time-consuming functions. However, if using imperative programming in these "inner loop" procedures places them in IO monad, the "outer loops" (the rest of the program - procedures that call it) will have to go there as well. This makes me doubt the Haskell approach to functional programming. If anyone has a version of the N-body benchmark, where the simulation is a type-safe pure function, I would very much like to see and time it.

6 15

Monad for HOAS?
by Edsko de Vries 15 May '08

15 May '08

Hi, Suppose we have some data structure that uses HOAS; typically, a DSL with explicit sharing. For example: > data Expr = One | Add Expr Expr | Let Expr (Expr -> Expr) When I use such a data structure, I find myself writing expressions such as > Let foo $ \a -> > Let bar $ \b -> > Add a b It seems to me that there should be a monad here somewhere, so that I can write this approximately like do a <- foo b <- bar return (Add a b) or something along those lines. It is however not at all clear to me what this monad should look like. I have experimented with adding a type parameter to Expr, something like > data Expr a = One > | Add (Expr a) (Expr a) > | Let (Expr a) (Expr a -> Expr a) > | Place a which has the additional benefit of supporting catamorphisms; I have also experimented with defining various variations on > Let a b = Let a (a -> b) and making Let an instance of Monad rather than Expr; but none of my experiments wered satisfactory. Am I missing something obvious, or is there a good reason this cannot be done? Thanks, Edsko

4 6

Re: Richer (than ascii) notation for haskell source?
by Patrick Surry 15 May '08

15 May '08

Lots of folk have suggested writing code with Unicode symbols, but that doesn't really get me where I'm thinking of. Back in the day, I spent many happy hours writing math(s) in amstex style, peppered with latex backslash references/macros for greek symbols, set operators as well as character attributes like underline, bold, goth, italic and so on. With the magic of (la)tex and dvips you get a rich intuitive representation of your equations - where you can 'see' types by character attributes (bold vectors, gothic sets or whatever) and have easily readable operators, functions, etc. Similarly to display alternative pattern cases as a display equation? So maybe what I really want is to essentially write my source in (la)tex and be able to both compile and render to dvi at the same time? I suppose word's crazy equation editor or mathml is another option but it makes the source itself either less portable or less readable? I think Knuth talks about literate programming as this ability to intermingle 'beautified' human-readable representation along with code, and it seems like Haskell is close to delivering that. (Tho I think "literate Haskell" is not the same thing.) Perhaps a pipe dream tho. Patrick ________________________________________________________________________ DISCLAIMER: This e-mail is intended only for the addressee named above. As this e-mail may contain confidential or privileged information, if you are not the named addressee, you are not authorised to retain, read, copy or disseminate this message or any part of it. If you received this email in error, please notify the sender and delete the message from your computer.

2 1

RE: Richer (than ascii) notation for haskell source?
by Patrick Surry 15 May '08

15 May '08

Sorry, missed a mail digest: LyX and lhs2tex sound more like what I mean. Patrick -----Original Message----- From: Patrick Surry Sent: Wednesday, May 14, 2008 10:24 PM To: 'haskell-cafe(a)haskell.org' Subject: Re: Richer (than ascii) notation for haskell source? Lots of folk have suggested writing code with Unicode symbols, but that doesn't really get me where I'm thinking of. Back in the day, I spent many happy hours writing math(s) in amstex style, peppered with latex backslash references/macros for greek symbols, set operators as well as character attributes like underline, bold, goth, italic and so on. With the magic of (la)tex and dvips you get a rich intuitive representation of your equations - where you can 'see' types by character attributes (bold vectors, gothic sets or whatever) and have easily readable operators, functions, etc. Similarly to display alternative pattern cases as a display equation? So maybe what I really want is to essentially write my source in (la)tex and be able to both compile and render to dvi at the same time? I suppose word's crazy equation editor or mathml is another option but it makes the source itself either less portable or less readable? I think Knuth talks about literate programming as this ability to intermingle 'beautified' human-readable representation along with code, and it seems like Haskell is close to delivering that. (Tho I think "literate Haskell" is not the same thing.) Perhaps a pipe dream tho. Patrick ________________________________________________________________________ DISCLAIMER: This e-mail is intended only for the addressee named above. As this e-mail may contain confidential or privileged information, if you are not the named addressee, you are not authorised to retain, read, copy or disseminate this message or any part of it. If you received this email in error, please notify the sender and delete the message from your computer.

1 0

Re: GHC predictability
by Don Stewart 15 May '08

15 May '08

> I offer up the following example: > > mean xs = sum xs / length xs > > Now try, say, "mean [1.. 1e9]", and watch GHC eat several GB of RAM. (!!) But you know why, don't you? > sat down and spent the best part of a day writing an MD5 > implementation. Eventually I got it so that all the test vectors work > right. (Stupid little-endian nonsense... mutter mutter...) When I tried > it on a file containing more than 1 MB of data... ooooohhhh dear... Did you use Data.Binary or the other libraries for efficient access to gigabytes of data? > Of course, the first step in any serious attempt at performance improvement > is to actually profile the code to figure out where the time > is being spent. Well, actually, for our 'mean()' case, it means just using the right structures. Arrays for example: import Data.Array.Vector import Text.Printf mean :: UArr Double -> Double mean arr = b / fromIntegral a where k (n :*: s) a = n+1 :*: s+a a :*: b = foldlU k (0 :*: 0) arr :: (Int :*: Double) main = printf "%f\n" . mean $ enumFromToFracU 1 1e9 For example, $ time ./A 5.00000000067109e8 ./A 3.53s user 0.00s system 99% cpu 3.532 total Try allocating an array of doubles in C, and getting similar results. (The compiler is optimising this to: Main_zdszdwfold_info: leaq 32(%r12), %rax cmpq %r15, %rax movq %rax, %r12 ja .L10 movsd .LC0(%rip), %xmm0 ucomisd %xmm5, %xmm0 jae .L12 movq %rsi, (%rax) movq $base_GHCziFloat_Dzh_con_info, -24(%rax) movsd %xmm6, -16(%rax) movq $base_GHCziBase_Izh_con_info, -8(%rax) leaq -7(%rax), %rbx leaq -23(%rax), %rsi jmp *(%rbp) .L12: movapd %xmm6, %xmm0 addq $1, %rsi subq $32, %r12 addsd %xmm5, %xmm0 addsd .LC2(%rip), %xmm5 movapd %xmm0, %xmm6 jmp Main_zdszdwfold_info Note even any garbage collection. This should be pretty much the same performance-wise as unoptimised C. > almost any nontrivial program you write > spends 60% or more of its time doing GC rather than actual work. Ok, you're doing something very wrong. GC time is typically less than 15% of the running time of typical work programs I hack on. I bet you're using lists inappropriately? > I find it completely impossibly to write code that doesn't crawl along at a > snail's pace. Even when I manage to make it faster, I usually have no clue > why. I think there is a problem that few people are taking the time to understand the compilation model of Haskell, while they've had the C runtime behaviour drilled into their brains since college. Until you sit down and understand what your Haskell code means, it will be very hard to reason about optimisations, unfortunately. GHC does what it does well, and its predictable. As long as you understand the operations your trying to make predictions about. I suggest installing ghc-core, and looking at how your code is compiled. Try many examples, and have a good knowledge of the STG paper. -- Don

8 12

Monad vs ArrowChoice
by Ronald Guida 14 May '08

14 May '08

I have read that Monad is stronger than Idiom because Monad lets me use the results of a computation to choose between the side effects of alternative future computations, while Idiom does not have this feature. Arrow does not have this feature either. ArrowChoice has the feature that the sum type, Either, can be used to choose between alternative computations, including their side effects. I know that Monad is supposed to be stronger than ArrowChoice, but I have to ask, what exactly can Monad do that ArrowChoice can't do? Let me set up an example to illustrate where I'm coming from. > import Control.Monad.Writer > import Control.Applicative > import Control.Arrow hiding (pure) The missileControl function accepts a flag to determine whether missiles actually get launched, and it returns the number of casualties. > missileControl :: Bool -> IO Integer > missileControl b = do > showFlag b > casualties <- if b > then launchMissiles > else doNotLaunch > return casualties > showFlag :: Bool -> IO Bool > showFlag b = (putStrLn $ "Launch flag = " ++ show b) >> return b > launchMissiles :: IO Integer > launchMissiles = do > putStrLn "Missiles have been launched." > putStrLn "Casualties = 6,700,000,000." > return 6700000000 > doNotLaunch :: IO Integer > doNotLaunch = putStrLn "Missiles not launched." >> return 0 If I try to use an Idiom, or even an Arrow, instead of a Monad, then I don't get to choose between the alternative side effects, and the results will be similar to this: > missileControl' :: Bool -> IO Integer > missileControl' b = do > showFlag b > casualties <- launchMissiles > casualties' <- doNotLaunch > if b > then return casualties > else return casualties' If I use ArrowChoice, then I can do this: > missileControl2 :: Bool -> IO Integer > missileControl2 b = runKleisli a b > where a = (Kleisli $ showFlag) >>> (arr boolToEither) >>> > ((Kleisli $ const launchMissiles) ||| > (Kleisli $ const doNotLaunch)) > boolToEither :: Bool -> Either () () > boolToEither True = Left () > boolToEither False = Right () GHCi> missileControl2 True Launch flag = True Missiles have been launched. Casualties = 6,700,000,000. 6700000000 GHCi> missileControl2 False Launch flag = False Missiles not launched. 0

2 1

Copy on read
by Andrew Coppin 14 May '08

14 May '08

I just had a random idea, which I thought I'd share with you all. I've heard about systems that do "copy on write". That is, all users share a single copy of some structure, until somebody tries to write on it. At that moment they get a personal copy to modify so they don't upset everybody else. This way, you don't have to go to all the expense of copying a potentially large structure unless it's actually necessary to do so. Then I started thinking about Clean's "uniqueness typing". If I'm understanding this correctly, it lets you do things like mutate data in-place without requiring a monad. The restriction is that the compiler has to be satisfied, at compile-time, that you will never try to access the old data you just overwrote. Although I once held more optimistic beliefs, as far as I can tell no current, real-world Haskell implementation ever mutates the fields of algebraic data types in-place. (Ignoring for a moment the issue of overwriting a thunk with it's result.) This strikes me as rather pessimistic. I was thinking... If Haskell had uniqueness typing, maybe the compiler could be made to infer when values are used in a unique way. And maybe if the compiler can detect data being used in a unique way, it could code for in-place updates instead of copying, and thereby gain a performance advantage. I don't know how viable this would be - the thing that immediately jumps out at me is that in practice there might be comparatively few places where you can *guarantee* the transformation is safe, and so it might not get applied very much. And considering all this would likely take a fair bit of work on the compiler, that wouldn't be a great payoff. Still, the idea of the compiler transparently rewriting your pure functional code to efficient mutable updates (when safe) is very appealing for performance reasons. Thoughts, people? [I'd be surprised if I'm the first person ever to have this idea...]

6 7

Data.Dynamic over the wire
by Jules Bean 14 May '08

14 May '08

> {-# LANGUAGE ScopedTypeVariables #-} Data.Dynamic gives a passable impression of adding support for dynamically typed code and runtime typing to GHC, without changing the basic statically typed, all types known at runtime nature of the language. Note that Data.Dynamic relies upon two things: it relies upon a concrete representation of types, given by TypeRep, and a primitive which has to be provided by the compiler to actually implement fromDynamic. (In GHC it uses unsafeCoerce# which is already available, but you could imagine providing other primitives). In principle TypeReps could be derived by hand, although if you do so you can break everything by providing invalid instances. In practice we'd rather the compiler did it for us and guaranteed safety. You can do all sorts of things with Dynamic, but the general pattern is that data which has some fixed, known type, can be passed through a chunk of code which doesn't know its type (wrapped in Dynamic) and then eventually consumed by another piece of code which *does* know the type, and can unwrap it. The consuming code has to know the type to unwrap it, although it can 'guess' various alternatives if it wants, and thus type safety is preserved. One thing which you can't obviously do is write Read or Show instances for Dynamic. So can we pass Dynamic data over the wire? If not, Dynamic is limited to the context of "within a single program", and can't be used over the network between cooperating programs, or in file formats, etc. You can try this: > import Data.Typeable > data SerialisedDynamic = SD TypeRep String deriving (Show) > freeze :: (Show a, Typeable a) => a -> SerialisedDynamic > freeze x = SD (typeOf x) (show x) > thaw :: forall a . (Read a, Typeable a) => SerialisedDynamic -> Maybe a > thaw (SD t s) = if typeOf (undefined :: a) == t then > Just (read s) > else Nothing This is close, and works as far as it goes. It is a limited reimplementation of Dynamic which uses show/read instead of unsafeCoerce#. As such it is pure haskell (but relies on Typeable instances). You can't finish it off because you can't derive a 'Read' instance for SD, because there is no read instance for TypeRep. Off-hand I can't think of any reason why there can't be a Read instance for TypeRep, but it would be a bit tricky with the current TypeRep because of the way its implemented, I think. You need to take care about globally qualified types and might want to use package names like ghc does in its linking phase, but those are definitely surmountable problems. Having said all that, I'm not sure how useful this really is. Most of the time you could use this, you could equally just pass around the String and 'read' it once you get to the place where you want to use the value. Practical over-the-wire protocols necessarily have some kind of tagging mechanism, and all this adds is a global "tag table" for Typeable types via TypeRep. Jules

5 4

Using Template Haskell to make type-safe database access
by Mads Lindstrøm 14 May '08

14 May '08

Hi, I was wondering if anybody had experimented with using Template Haskell (TH) and ordinary SQL to make type-safe database access? To clarify what I am thinking about I will sketch how it could be done. The TH function should take two inputs. SQL (as a string) and a database source name (DSN). It should return an IO action as output. The TH-function should: 1. Connect to the database using the DSN 2. Ask the database which types will be returned from the expression 3. Build an IO action which can be used to execute the SQL at run-time. The action could return the result as a (lazy) list. Due to step two we can make the returned values type-safe. Greetings, Mads Lindstrøm

4 9

Re: [Haskell-cafe] Richer (than ascii) notation for haskell source?
by Andrew Coppin 14 May '08

14 May '08

Reinier Lamers wrote: > > Op 14-mei-2008, om 20:32 heeft Andrew Coppin het volgende geschreven: >> Personally, I'd just like to be able to get rid of "->", "\" and >> other such hacks. Would it be possible to amend GHC so that it >> accepts "->" and [whatever the Unicode codepoint for "left arrow" is] >> and treats both the same? > I believe GHC already accepts "∀" instead of "forall", and some other > Unicode neatness. However, you can't use "λ" for "\" because "λ" is a > lowercase letter and thus valid in identifiers. So getting rid of "\" > might be impossible even with Unicode. Ooo... well spotted on that subtly edge case with lambda... Damn, that's just too bad. Using a backslash makes it look like a character escape or something. It's really quite ugly...

1 0