- Haskell-Cafe - Haskell.org

Why I Love Haskell In One Simple Example
by John Goerzen 28 Jun '05

28 Jun '05

I posted this on my blog at http://changelog.complete.org/node/339 but I thought there may be some here that would find it of use. I recently implemented some new Haskell numeric types that, instead of performing calculations, can generate a rendering of the requested calculation or store units with it. Here you see a transcript of my session with a Haskell interpreter. The mathematical statements I am entering after the ">" are standard Haskell expressions, and, as I demonstrate, normally evaluate to a single result. Once I get a more powerful simplifier, I will probably write a LaTeX exporting function as well. The entire implementation of this, BTW, is less than 200 lines. NumTest> 5 + 1 * 3 8 NumTest> prettyShow $ 5 + 1 * 3 "5+(1*3)" NumTest> rpnShow $ 5 + 1 * 3 "5 1 3 * +" NumTest> prettyShow $ 5 + 1 * 3 "5+(1*3)" NumTest> prettyShow $ simplify $ 5 + 1 * 3 "5+3" NumTest> prettyShow $ 5 * (Symbol "x") + 3 "(5*x)+3" NumTest> 5 / 2 2.5 NumTest> (units 5 "m") / (units 2 "s") 2.5_m/s NumTest> (units 5 "m") / 2 2.5_m NumTest> 10 * (units 5 "m") / (units 2 "s") 25.0_m/s NumTest> sin (pi/2) 1.0 NumTest> sin (units (pi/2) "rad") 1.0_1.0 NumTest> sin (units 90 "deg") 1.0_1.0 NumTest> (units 50 "m") * sin (units 90 "deg") 50.0_m NumTest> ((units 50 "m") * sin (units 90 "deg")) :: Units (SymbolicManip Double) 50.0*sin(((2.0*pi)*90.0)/360.0)_m NumTest> rpnShow $ dropUnits $ ((units 50 "m") * sin (units 90 "deg")) "50.0 2.0 pi * 90.0 * 360.0 / sin *" NumTest> (units (Symbol "x") "m") * sin (units 90 "deg") x*sin(((2.0*pi)*90.0)/360.0)_m Also, I defined this in my source file: test :: forall a. (Num a) => a test = 2 * 5 + 3 Now, it can be used: NumTest> test 13 NumTest> rpnShow test "2 5 * 3 +" NumTest> prettyShow test "(2*5)+3" NumTest> test + 5 18 NumTest> prettyShow (test + 5) "((2*5)+3)+5" NumTest> rpnShow $ test + 5 "2 5 * 3 + 5 +" You can grab the very early experimental code with darcs get http://darcs.complete.org/num. Haskell has no built-in support for numeric types with units, arbitrary symbols carried through computations, etc. But it was trivial to add it. This kind of extensibility is a key part of why Haskell is so amazing.

5 6

RE: [Haskell-cafe] Compiling an extremely large Haskell file (in GHC)
by Simon Marlow 27 Jun '05

27 Jun '05

On 27 June 2005 19:24, Arjun Guha wrote: > I have an extremely large source file of about 11 MB. It's the > all-pairs shortest paths data for a map of the Hyde Park area of > Chicago (no real reason, really). I generated information in Scheme > and printed the result to a Haskell source file as a list. I then > edited the file to initialized an array with the data. > > GHC, with a 200MB stack, took up 1 hour and 1.3 GB of memory before > getting killed by the system. How would I compile something of this > size? I need to have the array of all-pairs shortest paths > pre-computed. Any suggestions? GHC doesn't have a good way to compile large amounts of static data. Either: (a) put the data into a static array in a C file, compile it with a C compiler, and access it via the FFI, or (b) encode it as a string, and access it using GHC's primitives, or (c) read it from a file at runtime. (Happy and Alex use (b) for encoding parse tables, BTW). Cheers, Simon

1 0

Why distinct tyvars in instance declarations?
by Josh Hoyt 27 Jun '05

27 Jun '05

Hello, I'm a new Haskeller, and I'm running into a problem attempting to declare certain types as instances. I was attempting something that's effectively equivalent to: > class Foo a > > instance Foo (Either b b) but GHC complains: > Illegal instance declaration for `Foo (Either b b)' > (The instance type must be of form (T a b c) > where T is not a synonym, and a,b,c are distinct type variables) > In the instance declaration for `Foo (Either b b)' and so I looked in the report (http://www.haskell.org/onlinereport/decls.html#sect4.3.2) and found: > The general form of the corresponding instance declaration is: > > instance cx' => C (T u1 ... uk) where { d } > > where k>=0. The type (T u1 ... uk) must take the form of a type constructor T applied to simple type variables u1, ... uk; furthermore, T must not be a type synonym, and *the ui must all be distinct*. (emphasis mine) My question is, why this restriction that the types must be distinct? In particular, I'd like to declare a very specific type (Either String String) as an instance. What techniques can I use to accomplish this? Josh Hoyt

3 3

Re: [Haskell-cafe] Why distinct tyvars in instance declarations?
by Frank-Andre Riess 27 Jun '05

27 Jun '05

Hi there, > but GHC complains: > > Illegal instance declaration for `Foo (Either b b)' > > (The instance type must be of form (T a b c) > > where T is not a synonym, and a,b,c are distinct type variables) > > In the instance declaration for `Foo (Either b b)' unless I'm totally mistaken, your problem isn't the distinction thingy, but rather an error like supplying an Int for where you need (Int -> Int -> Int). That is, you're trying make (Either String String) an instance of Foo, (Either String String) already being a fully constructed type; Foo, on the other hand, seems to require a type constructor that is yet to parameterize over three more types (e.g. StateT). Greets, Frank-Andre Riess

3 2

Re: [Haskell-cafe] Noob error: Type b -> c b Does not match IO a
by kynn＠panix.com 27 Jun '05

27 Jun '05

Some simplifications might help you here... > prodList [] = 1 > prodList (0:xs) = 0 > prodList (x:xs) = x * prodList xs Simplified: prodList xs = foldl (*) 1 xs But my original at least made some provision for short circuiting the whole operation if the list contained a 0. As far as I can figure, fold, map, etc., are not suitable for any situation in which short-circuiting would be desirable (e.g. and, or, etc.). Am I wrong? (I realize that, given that the function product is already available, there is no point in defining my function prodList above, but my question is a more general one, having to do with how best to implement short-circuiting.) Thanks! kj

6 8

type inference and named fields
by Malcolm Wallace 27 Jun '05

27 Jun '05

I have discovered something I believe to be a problem in Haskell'98, although it is not a simple bug as such - it has more of the flavour of an unintended mismatch in the interaction of two separate features. Since Haskell is deeply principled language, a feature conflict is extremely rare, and so worthy of note. So here it is: Some attempts to use named field updates are prohibited by type inference, even though the code is perfectly type safe. Here is an example. > module Fieldbug where > data Fields a = > VariantWithTwo { field1 :: a > , field2 :: a } > | VariantWithOne { field1 :: a } The key point here is that the data structure with named fields has more than one constructor, and some fields are omitted in one of the variants. Now let's try to write a simple conversion function over values of this type, using only the named-field update style: > data Void = Void > > voidcast :: Fields a -> Fields Void > voidcast v@(VariantWithTwo{}) = v { field1 = Void , field2 = Void } > voidcast v@(VariantWithOne{}) = v { field1 = Void } It looks simple enough doesn't it? But none of the widely available Haskell implementations will accept this code. Hugs: ERROR "Fieldbug.hs":11 - Inferred type is not general enough *** Expression : voidcast *** Expected type : Fields a -> Fields Void *** Inferred type : Fields Void -> Fields Void ghc: Fieldbug.hs:11:32: Couldn't match the rigid variable `a' against `Void' `a' is bound by the type signature for `voidcast' Expected type: Fields Void Inferred type: Fields a In the record update: v {field1 = Void} In the definition of `voidcast': voidcast (v@(VariantWithOne {})) = v {field1 = Void} nhc98: ====== Errors after type inference/checking: Derived type for Fieldbug.voidcast at 10:1-11:42 does not match due to: given free variable a is bound to Void Derived:((Fields Void) -> (Fields Void)) Given :((Fields a) -> (Fields Void)) As far as I can tell, the problem is that in the final line, the expression v { field1 = Void } is interpreted by the type inference algorithm as if the variable v could contain either constructor VariantWithOne or VariantWithTwo. Obviously in the latter case the expression would indeed be incomplete because it casts only one of the fields, not both. But we know that can never be the case! By pattern-matching, this particular v /must/ be the former constructor. Unfortunately we cannot pass that knowledge into the type inference algorithm. It turns out that it is in fact /impossible/ to write this conversion function using only named field updates. It can only be written by using an explicit constructor on the rhs, which thus forces you to initialise all its fields explicitly. This negates any value from using named fields in the first place. Regards, Malcolm

10 32

RE: [Haskell-cafe] Re: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

> Off-hand, I recall a paper by Martin Odersky and the Scala people > discussing their approach to the Expression Problem, So ... http://icwww.epfl.ch/publications/documents/IC_TECH_REPORT_200433.pdf ... I guess The key innovative idea there is composition of mixins while replacing formal superclasses of mixins by the actual base class for mixin composition. I quote: "In a mixin composition A with B with C, class A acts as actual superclass of mixins B and C, replacing the declared superclasses of B and C. To maintain type soundness, A must be a subclass of the declared superclasses of B and C. A super reference in either B or C will refer to a member of class A. As is the case for trait composition, Scala's mixin composition is commutative in the mixins - A with B with C is equivalent to A with C with B." In OOHaskell, you would parameterize in the superclass and that's it. DISCLAIMER: we haven't tried this. Thanks for the inspiration. > and a related paper by Jacques Garrigue, > where he proposes to solve it using OCaml's polymorphic variants. I am not sure. Is this referring to "Objective Label"? Which paper exactly? > Hope this helps, It's interesting but I don't see how we make progress with the original (by now perhaps trivial) question regarding the transportation of an OO design into Haskell. The shapes problem doesn't call for Odersky's new contribution: I quote: "We add to this list the following criterion: * Independent extensibility: It should be possible to combine independently developed extensions so that they can be used jointly [21]." The shapes problem rather calls for silly subtyping polymorphism. So we are beating a dead horse (or a red herring) by detouring to Scala unless I don't get you were hinting at. BTW, I just notice that Oderksy's list of partial solutions isn't complete: - Visitor combinators (Joost Visser) complementing Palsberg et al. - Many forms of generic functional programming (Hinze etc.) - Haskell type classes allow for extension in both type and processor extension. It's getting late here. Ralf

2 1

RE: [Haskell-cafe] Re: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

Bulat wrote: > if you require several operations, you can pack them in tuple or > structure (really, tuple is a structure without field names) How are we going to anticipate all possible bodies of a for-loop? By comparison, when we build a normal Haskell list, does the construction precisely mirror what we are going to *do* with each element? Fold the map then!!! > if you need fields/interfaces inheritance, then this method will not > work. but in 90% of cases it's enough. What to do for the other 10%? > in C++, creating classes is the > most useful method of structuring program, so it is used for any > problem - from very simple to most complex. when you translate such > thing to Haskell, it's better to see which concrete problem are solved > with help of classes, and not to emulate the classes itself (because > in this case you will write many unneeded code) Yes, but we ought to solve the shapes problem. The shapes example is in Bulat's 10% region. > only because it's C-like :) you just can't believe that Haskell > program can be 3-10 times smaller while keeping the same functionality > :))) But note that "same functionality" is one thing, having "separate compilation" and "program extensibility" too is another one. Ralf

2 1

RE: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

Andreas Rossberg said: > [Followups to Haskell Cafe] > as far as I read it, "dynamic" or "late binding" is orthogonal to > subtyping, or typing in general. It is just that most typed OO languages > lump these concepts together. Absolutely agreed. > Often a simple first-class function, or a record thereof, > is enough (in fact, "dynamic binding" is just the OOO way > of saying "calling a first-class function"). In typical > functional programming style, you need the general > thing only rarely. Can you just tell how *you* would favor encoding the shapes example that was posed by poster? (It might just be that your code would be very close to Lennart's proposal?) Thanks, Ralf

2 1

RE: [Haskell-cafe] RE: Re[4]: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

I guess we just need to agree that we disagree. Of course, you are right that I am just a newbie when it comes to Haskell. How did you know that I am actually a Cobol programmer? Did you google? http://www.google.com/search?biw=1003&hl=en&q=Ralf+Cobol Seriously (?): 1. I never intended to impose any particular OO style on Haskeller's. Its more about the *intellectual* question whether we can take C++/C#/Java code and do a structure-preserving conversion to Haskell without starting to argue on paradigm conversion. Or as Alistair Bayley argues (Alistair, thanks for helping out!) http://www.haskell.org/tmrwiki/FpVsOo "... it might be that you need to interface with external OO code, or you are porting an existing program and need to remain faithful to the original design, if only because you don't understand it well enough to convert it to a functional design. ..." Bulat, why not read all of this? Also see the end of that Wiki page, where a reference to a paper is given, which seems to solve all these problems, but my brain is to small to really be sure. ;-) 2. No matter how much you try, the code that you showed was not very close to a faithful Shapes implementation. If you dare to read the spec: http://onestepback.org/articles/poly/ http://www.angelfire.com/tx4/cus/shapes/ You made two proposals that don't solve the problem no matter of *style*: 1st proposal of Bulat: > just create list of draw functions itself: > > [drawCircle (10,10) 5, drawSquare (20,20) 10] > > you are not expected that this problem can be solved with one line of code? :) My reply: you are not building a list of objects. You are not organizing a loop whose body iterates over a list and executes functionality. 2nd proposal of Bulat: > for more complex tasks - declare interface as a structure: > > data ShapeInterface = Shape { draw :: IO (), > moveTo :: Point -> IO (), > calcArea :: Float > } > > > and return this structures from "constructor" functions: > > circle x y r = Shape { draw = drawCircle center r, > moveTo newCenter = ...., > calcArea = pi*r*r > } > where center = Point x y > > square x y size = Shape { draw = ...., > moveTo newCenter = ...., > calcArea = size*szie > } > > figures = [circle 1 2 3, square 4 5 6, circle 7 8 9] The tragedy here is that this stops to work once circles and squares do have different interfaces. You solution does not scale. Subtyping allows for interface extension, and the actual benchmark exploits this, but your code avoids it. Anyway the solution is trivial: ex. quantification, you didn't propose that. Cheers, Ralf (back to Cobol) > -----Original Message----- > From: Bulat Ziganshin [mailto:bulatz@HotPOP.com] > Sent: Thursday, June 23, 2005 11:37 PM > To: Ralf Lammel > Cc: Pal-Kristian Engstad; haskell-cafe(a)haskell.org > Subject: Re: [Haskell-cafe] RE: Re[4]: [Haskell] Dynamic binding > > Hello Ralf, > > Thursday, June 23, 2005, 11:40:13 PM, you wrote: > > RL> a) building (i) a list of data is fundamentally different > RL> from building (ii) a list of anticipated results of each datum. > RL> I would be surprised to hear that this counts as a valid technique. > RL> BTW, you can do the *same* in a lazy OO language. (No lazy OO language > RL> at hand -- well lazyness can be simulated.) > > sorry, "valid" technique is technique that work :) i use in my own > program all the three ways i mentioned to solve problems of different > complexity > > afair, you are relatively new to Haskell (relatively to my 1-year > experience :) and, i think, you are not share FP thinking style. when > programming in Haskell, i think in terms "what thing i will need in > this point of program?". if i need, for example, a possibility to check > string against regular expression, then i will pass a function which > does this check, not original RE. if i need a possibility to > draw a shape, i will pass action which draws this shape. if i need > several functions, i just combine them in a tuple > > there is one interesting example in my program. i have a list of > wildcards and list of filenames and for each filename i need to know > number of first wildcard to which this filename matched. in early > stages of my program development i just passed list of wildcards to > file-finding routine (as [Wildcard]). then, i changed list of wildcards > to list of functions which check match against each wildcard > ([Filename->Bool]). and after that, i changed this to one function which > just finds first True answer (Filename->Int). it was also more > effective to compute this function only one time (it was something > compiled > on moment of computing and worked as fast as hand-written analyzer for > given set of wildcards) > > as you see, i slowly migrated from traditional way of solving this > problem to perfectly functional way and it was required several months > > RL> a) building (i) a list of data is fundamentally different > RL> from building (ii) a list of anticipated results of each datum. > > i think that you don't have "Haskell brain" ;) and therefore don't > "trust" functions, which are passed as parameters, collected in lists, > saved in data structures and so on. you are prefer to "put hands on" > some data, preferably an object, which can be manipulated with any > method declared in his interface. i'm right? ;) > > FP encourage another way - passing functions which will then be applied to > some additional arguments, as in my program, where file-finding > function absolutely don't need list of wildcards. it just need to map > filename to wildcard number, so a Filename->Int parameter is just > enough > > in the draw example, each elment in a list was an action (having type > IO() ), so i don't create list of anticipated results, i created list > of actions which can be performed, for example, by sequence_ > > > RL> Anyway, even if people end up coding as you propose, > RL> it won't work in general. Think of mutation methods that > RL> change the state but preserve the type. Then your list will > RL> still be heterogonous. NO? > > my second example was just of this type. it uses IORefs to hold > current state, but this IORefs don't need to appear in interface > > see method moveTo, which changes state variable center, and method > draw, which uses this variable > > >> this state is just don't need to appear in interface definition :) > >> circle x y r > > RL> You are not talking about state but constructor arguments. > > "interface definition" is a structure ShapeInterface, which have only > fields for exposed object methods. so it supports any figures in > universe :) > > RL> In OO, mutable state tends to leak to the interface, > RL> perhaps not as public fields, perhaps not even as public > > only in C++ and other languages which need to calculate object size :) > declaration of _non-public_ fields in _interface_ is something strange > ;) > > >> this state is just don't need to appear in interface definition :) > >> > >> if you need to maintain mutable state, this is also not a problem: > >> > >> data ShapeInterface = Shape { draw :: IO (), > >> moveTo :: (Int,Int) -> IO (), > >> calcArea :: Float > >> } > >> circle x y r = do > >> center <- ref (x,y) > >> return Shape { draw = val center >>= drawCircle r > >> , moveTo = (center=:) > >> , calcArea = pi*r*r > >> } > >> main = do > >> figures <- sequence [circle 1 2 3, square 4 5 6, circle 7 8 9] > >> mapM_ draw figures > >> mapM_ (moveTo (0,0)) figures > >> mapM_ draw figures > >> > >> ref=newIORef > >> val=readIORef > >> (=:)=writeIORef > > > > -- > Best regards, > Bulat mailto:bulatz@HotPOP.com > >

1 0