- Haskell-Cafe - Haskell.org

-- Extension for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell -- Extension for "Pearls of Functional Algorithm Design" by Richard Bird, -- 2010, page 25 #Haskell -- This version assumes 3 disjoint ordered sets represented as sorted arrays.ts.
by caseyh＠istar.ca 29 Apr '11

29 Apr '11

-- Extension for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell -- O(log|X|+log|Y|+log|Z|) performance -- Question: is there a way to get the type signature as the following: -- smallest :: (Ord a) => Int -> [Array Int a] -> a module SelectionProblem where import Data.Array import Data.List -- Works on 2 finite ordered disjoint sets represented as sorted arrays. smallest :: (Ord a) => Int -> (Array Int a, Array Int a) -> a smallest k (xa,ya) = ~~~~search k (xa,ya) (0,m+1) (0,n+1) ~~~~~~~~where ~~~~~~~~(0,m) = bounds xa ~~~~~~~~(0,n) = bounds ya -- Removed some of the "indexitis" at the cost of calling another function. search :: (Ord a) => Int -> (Array Int a, Array Int a) -> (Int,Int) -> (Int,Int) -> a search k (xa,ya) (lx,rx) (ly,ry) ~~~~| lx == rx = ya ! (k+ly) ~~~~| ly == ry = xa ! (k+lx) ~~~~| otherwise = case (xa ! mx < ya ! my) of ~~~~~~~~~~~~~~~~~~~~~~(True) -> smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) ~~~~~~~~~~~~~~~~~~~~~~(False) -> smallest2h k (ya,xa) ((ly,my,ry),(lx,mx,rx)) ~~~~~~~~~~~~~~~~~~where ~~~~~~~~~~~~~~~~~~~~~~mx = (lx+rx) `div` 2 ~~~~~~~~~~~~~~~~~~~~~~my = (ly+ry) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array and ya the second array by their middle elements. smallest2h :: (Ord a) => Int -> (Array Int a, Array Int a) -> ((Int,Int,Int),(Int,Int,Int)) -> a smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) = ~~~~case (k<=mx-lx+my-ly) of ~~~~~~(True) -> search k (xa,ya) (lx,rx) (ly,my) ~~~~~~(False) -> search (k-(mx-lx)-1) (xa,ya) (mx+1,rx) (ly,ry) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- Works on 3 finite ordered disjoint sets represented as sorted arrays. smallest3 :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> a smallest3 k (xa,ya,za) = ~~~~-- On each recursive call the order of the arrays can switch. ~~~~search3 k (xa,ya,za) (0,bx+1) (0,by+1) (0,bz+1) ~~~~~~~~where ~~~~~~~~(0,bx) = bounds xa ~~~~~~~~(0,by) = bounds ya ~~~~~~~~(0,bz) = bounds za -- Removed some of the "indexitis" at the cost of calling another function. search3 :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> ~~~~~~~~~~~~(Int,Int) -> (Int,Int) -> (Int,Int) -> a search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,rz) ~~~~| lx == rx && ly == ry = za ! (k+lz) ~~~~| ly == ry && lz == rz = xa ! (k+lx) ~~~~| lx == rx && lz == rz = ya ! (k+ly) ~~~~| lx == rx = search k (ya,za) (ly,ry) (lz,rz) ~~~~| ly == ry = search k (xa,za) (lx,rx) (lz,rz) ~~~~| lz == rz = search k (xa,ya) (lx,rx) (ly,ry) ~~~~| otherwise = case (xa ! mx < ya ! my, xa ! mx < za ! mz, ya ! my < za ! mz) of ~~~~~~~~~~~~~~~~~~~~~~(True, True, True) -> smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) -- a<b<c ~~~~~~~~~~~~~~~~~~~~~~(True, True, False) -> smallest3h k (xa,za,ya) ((lx,mx,rx),(lz,mz,rz),(ly,my,ry)) -- a<c<b ~~~~~~~~~~~~~~~~~~~~~~(False, True, True) -> smallest3h k (ya,xa,za) ((ly,my,ry),(lx,mx,rx),(lz,mz,rz)) -- b<a<c ~~~~~~~~~~~~~~~~~~~~~~(False, False, True) -> smallest3h k (ya,za,xa) ((ly,my,ry),(lz,mz,rz),(lx,mx,rx)) -- b<c<a ~~~~~~~~~~~~~~~~~~~~~~(True, False, False) -> smallest3h k (za,xa,ya) ((lz,mz,rz),(lx,mx,rx),(ly,my,ry)) -- c<a<b ~~~~~~~~~~~~~~~~~~~~~~(False, False, False) -> smallest3h k (za,ya,xa) ((lz,mz,rz),(ly,my,ry),(lx,mx,rx)) -- c<b<a ~~~~~~~~~~~~~~~~~~where ~~~~~~~~~~~~~~~~~~~~~~mx = (lx+rx) `div` 2 ~~~~~~~~~~~~~~~~~~~~~~my = (ly+ry) `div` 2 ~~~~~~~~~~~~~~~~~~~~~~mz = (lz+rz) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array, ya the second array, and za the third array by their middle elements. smallest3h :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> ~~~~~~~~((Int,Int,Int),(Int,Int,Int),(Int,Int,Int)) -> a smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) = ~~~~case (k<=mx-lx+my-ly+mz-lz) of ~~~~~~(True) -> search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,mz) ~~~~~~(False) -> search3 (k-(mx-lx)-1) (xa,ya,za) (mx+1,rx) (ly,ry) (lz,rz) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- To convert a list into an array indexed from 0. xa = listArray (0, length xs - 1) xs ya = listArray (0, length ys - 1) ys za = listArray (0, length zs - 1) zs xs = [0,17..90] ys = [1,13..69] zs = [7,24..91] ua = listArray (0, length us - 1) us va = listArray (0, length vs - 1) vs wa = listArray (0, length ws - 1) ws us = [0,17..100] vs = [101,121..200] ws = [201,221..300] -- *SelectionProblem> sort (xs++ys++zs) -- [0,1,7,13,17,24,25,34,37,41,49,51,58,61,68,75,85]

1 0

Trouble installing FileManipCompat
by Tony Miller 28 Apr '11

28 Apr '11

Hi, I'm trying to install FileManipCompat(well, really HStringTemplateHelpers, but the error is from FileManipCompat) and I'm getting this error: [1 of 1] Compiling System.FilePath.FindCompat ( System/FilePath/FindCompat.hs, dist/build/System/FilePath/FindCompat.o ) System/FilePath/FindCompat.hs:175:20: Not in scope: data constructor `State' I've attached the complete output of `cabal --verbose install HStringTemplateHelpers`.

3 4

ANNOUNCE: cereal-0.3.3.0
by Trevor Elliott 28 Apr '11

28 Apr '11

Hot on the heels of the last release, cereal-0.3.3.0 [1] adds support for parsing and rendering lazy ByteStrings. Most running functions in Data.Serialize.Get and Data.Serialize.Put now have lazy analogues, and Data.Serialize has gained encodeLazy and decodeLazy. This new functionality was made possible by the incremental parsing support added in cereal-0.3.1.0 by Lemmih. [1] http://hackage.haskell.org/package/cereal-0.3.3.0

2 2

Re: [Haskell-cafe] [Haskell] ANNOUNCE: zeno-0.2
by Benedict Eastaugh 28 Apr '11

28 Apr '11

Hi Will, I attended your presentation on Zeno at AngloHaskell last year and was really intrigued; it's great to see you've got a release up on Hackage, and I look forward to trying it out. Are you planning on making your source code repository publicly available on GitHub or somewhere similar? If nothing else it would be interesting to follow further developments between releases. All the best, Benedict.

2 1

Re: [Haskell-cafe] Python is lazier than Haskell
by Dan Doel 28 Apr '11

28 Apr '11

(Sorry if you get this twice, Ertugrul; and if I reply to top. I'm stuck with the gmail interface and I'm not used to it.) On Thu, Apr 28, 2011 at 11:27 AM, Ertugrul Soeylemez <es(a)ertes.de> wrote: > I don't see any problem with this. Although I usually have a bottom-up > approach, so I don't do this too often, it doesn't hurt, when I have to. I do. It's low tech and inconvenient. Whenever I program in Haskell, I miss Agda's editing features, where I can write: foo : Signature foo x y z = ? Then compile the file. The ? stands in for a term of any type, and becomes a 'hole' in my code. The editing environment will then tell me what type of term I have to fill into the hole, and give me information on what is available in the scope. Then I can write: foo x y z = { partialImpl ? ? } and execute another command. The compiler will make sure that 'partialImpl ? ?' has the right type to fill in the hole (with ?s again standing in for terms of arbitrary type). If the type checking goes through, it expands into: foo x y z = partialImpl { } { } and the process repeats until my function is completely written. And of course, let's not forget the command for automatically going from: foo x y z = { x } to foo Con1 y z = { } foo Con2 y z = { } foo Con3 y z = { } ... I don't think there's anything particularly Agda-specific to the above. In fact, the inference required should be easier with Haskell/GHC. Features like this would be pretty killer to have for Haskell development; then I wouldn't have to prototype in Agda. :) -- Dan

3 2

There is no null; Maybe/Option types
by Christopher Done 28 Apr '11

28 Apr '11

Hi Cédric, I saw your post on Maybe types wondering what the point of it is and why anyone would want it. I thought I'd reply by email as I don't want to infringe on your freedom of expression. If you find that I'm saying things you already know, please scroll down to the bottom, which addresses your final question. I'm CC'ing the Haskell mailing list. I wrote a lot and I might as well share it. Quotes below are from: http://beust.com/weblog/2010/07/28/why-scalas-option-and-haskells-maybe-typ… > If you read the voluminous material that describes the concepts behind the > Option class, there are two main benefits: > > - It saves you from NullPointerException > - It allows you to tell whether null means “no object” or “an object > whose value is null” > > The second point is true, as you probably already understand: - Nothing is different from False. - They also have distinct, completely un-unifiable types. Nothing is type Maybe something, False is type Bool. - Maybe Int is also distinct from Maybe String. The latter point is true in a sense, but I think the problem and the solution aren't the same for Haskell and Java. I can't speak for Java because I don't know it, I know C#, which I know from a lot of experience does have nullable objects and thus null pointer exceptions. I assume everything below can be applied to Java, please tell me if not. - *No* value in Haskell can be null/empty. - *All* values in C# can be null/empty. - Therefore if C#'s values were completely explicit, and they might be defined, in Haskell, as: - data CObject a = TheValue a | Null - I'm assuming you know a bit of Haskell or can just figure it out easily enough. Read as: the type CObject, for all types, a, can be represented by either a value of type a, or null. - So a value of type int can be inhabited by either 123 or null. - Notice, of course, that this is the same as the definition of Maybe: data Maybe a = Just a | Nothing. - Therefore, in Haskell's context, it's not that Maybe saves you from null pointers, it's that it *allows you to express* nullability in a language without implicit nullability, which is default for all values in C#. I suspect the crux of the problem is that Java and C# have implicit nullability. It's also worth noting that the Maybe type in Haskell *can* *also* cause something similar "null pointer exceptions"; if you use the function fromJust, which just takes from a Maybe value and throws an exception if there's nothing in it. And, indeed, this function is a very common cause of exceptions in Haskell. A simple Google shows 870 results of this exception: http://www.google.com/#q="Exception:+Maybe.fromJust%3A+Nothing"<http://www.google.com/#q=%22Exception:+Maybe.fromJust%3A+Nothing%22>Also similar is use of the head function, which takes the first element of a list or throws an exception is the list is empty: http://www.google.com/#q="Exception:+Prelude.head%3A+empty+list"<http://www.google.com/#q=%22Exception:+Prelude.head%3A+empty+list%22>. 4,610 results. Most of the (non-IO) runtime errors I get using Haskell software is due to head or fromJust, it's actually quite annoying. That is the technical aspect and some background, for what it's worth. val result = map.get( "Hello" ) > > result match { > case None => print "No key with that name!" > case Some(x) => print "Found value" + x > } > > See what’s going on here? You avoid a NullPointerException by… testing > against null, except that it's called None. What have we gained, exactly? > > The worst part about this example is that it forces me to deal with the > null case right here. Sometimes, that's what I want to do but what if such > an error is a programming error (e.g. an assertion error) that should simply > never happen? > I believe here lies the problem. It's true; if your method expects a value not to be null then you shouldn't have to deal with it. - If the value is never ever supposed to be null, then you should be given a non-nullable value. - If the value is supposed to be nullable at some point, then your function is explictly giving the opportunity for optionality and should support it. If it barfs on a null value then it's not really satisfying the deal made with the caller that it supports nullable values. Unfortunately this is impossible in Java and C# because you can't have non-nullables. You also can't tell everyone to never use null and use a Maybe value, so C# or Java are more or less screwed on this point. > And you know what construct does exactly this? NullPointerException! Try > to reference a null pointer and that exception will be thrown. It will make > its way up the stack frames since you probably never catch it anywhere (nor > should you) and it will show you a clear stack trace telling you exactly > what happened and where. > The solution proposed for Java is for the method to barf on bad input at runtime. The solution of OCaml/Haskell is to barf at the caller of the function at development time; you're using the function incorrectly, and the developer's realised that he's using it incorrectly and immediately fixes it; the code never made it into testing or production. How much time did this save? I don't think anyone would argue that finding out later rather than now that we screwed up is desirable. > In this case, I just want to assume that I will never receive null and I > don't want to waste time testing for this case: my application should simply > blow up if I get a null at this point. > You can do that with fromJust, but it's generally considered bad practice, at least in the Haskell development world. Using fromJust brings enforcing constraints away from the compiler and into the hands of the developer who is flawed, busy and confused most of the time. These types of functions are called partial functions. A total function is a function that handles every case of a value given to it. So: > :t head head :: [a] -> a > :t listToMaybe listToMaybe :: [a] -> Maybe a > head [] *** Exception: Prelude.head: empty list > listToMaybe [] Nothing The former is partial, the latter is total. Code that uses partial functions is inherently partial in its entirety, leaving enforcing invariants on the programmer which could otherwise have been done by the compiler. *Static*: In Fantom, the fact that a variable can be null or not is captured > by a question mark appended to its type: Already covered; we both know Option/Maybe do this. > > - *Runtime*: The second aspect is solved by Fantom's "safe invoke" > operator, ?.. This operator allows you to dereference a null pointer > without receiving a null pointer exception: > // hard way > Str? email := null > if (userList != null) > { > user := userList.findUser("bob") > if (user != null) email = user.email > } > > // easy way > email := userList?.findUser("bob")?.email > > Note how this second example is semantically equivalent to the first > one but with a lot of needless boiler plate removed. > > So, can someone explain to me how Option addresses the null pointer > problem better than Fantom's approach? > Use of Fantom's save invoke and Maybe are more or less the same. -- Hard way email = if userList /= Nothing then let user = findUser "bob" (fromJust userList) in if user /= Nothing then getEmail (fromJust user) else Nothing else Nothing Note that I have to use fromJust because there is no implicit nullability. -- Easy way email = userList >>= findUser "bob" >>= getEmail This is semantically equivalent to the first one. There is also syntactic sugar for the above, for when you're not just chaining, but doing something complicated: -- Sugared way email = do list <- userList user <- findUser "bob" list email <- getEmail user return email If I'm using list or user or email more than once, this style is very useful. This is exactly equivalent to the above, it de-sugars into using the >>=function, which is pretty much the same as your use of ?., in this context. Cases and functions are just another way of accessing maybe values when you explicitly want to handle the null case. λ> maybe 4 (+2) (Just 5) 7 λ> maybe 4 (+2) Nothing 4 λ> case Just 5 of Just x -> x * 2; Nothing -> 0 10 I'm not saying it's the only way or the best way. It's certainly nice, though. P.S. Question: what would this code do and what would the compiler tell you about it? Str? email := null email = userList.findUser("bob").email

9 12

HipmunkPlayground compile error
by Andrew Pennebaker 28 Apr '11

28 Apr '11

$ system_profiler SPSoftwareDataType | grep "System Version" System Version: Mac OS X 10.6.7 (10J869) $ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.0.2 $ cabal --version cabal-install version 0.10.2 using version 1.10.1.0 of the Cabal library $ cabal install hipmunkplayground ... Updating documentation index /Users/andrew/Library/Haskell/doc/index.html cabal: Error: some packages failed to install: GLFW-0.4.2 failed during the building phase. The exception was: ExitFailure 1 HipmunkPlayground-5.2.0.3 depends on GLFW-0.4.2 which failed to install. Cheers, Andrew Pennebaker www.yellosoft.us

3 5

GHC repositories
by Andrew Pennebaker 28 Apr '11

28 Apr '11

Now that GHC has a git repository<http://hackage.haskell.org/trac/ghc/wiki/Repositories>, could that change be reflected in the docs<http://www.haskell.org/ghc/download> ? It's hard to work with folks on Trac to debug GHC when I can't find the latest version (changesets are now git, not svn). Cheers, Andrew Pennebaker www.yellosoft.us

1 0

Haskell Weekly News: Issue 179
by Daniel Santa Cruz 28 Apr '11

28 Apr '11

Welcome to issue 179 of the HWN, a newsletter covering developments in the Haskell community. This release covers the week of April 16 to 23, 2011. Announcements Alex Mason announced (http://goo.gl/2qtyM) the second annual Australian Haskell Hackathon to be heald from Friday July 8th to Sunday July 10th, at the UNSW's Computer Science building in Sydney. Come share with your fellow Australasian Haskellers! "The Hac" team invited us (http://goo.gl/8EQfI) to HacPhi 2011, a Haskell hackathon/get-together to be held July 29 to 31 at the University of Pennsylvania, in Philadelphia. Daniel Wagner wanted to stress that "everyone is welcome--you do not have to be a Haskell guru. Helping hack on someone else's project could be a great way to increase your Haskell-fu." Robert Clausecker asked "Is Hugs dead?" (http://goo.gl/639dC) Sad to see projects of this sort fade into the past. Quotes of the Week * copumpkin: THE POWER OF MIXFIX COMPELS YOU (to not use it much) Top Reddit Stories * Why Darcs users care about consistency Domain: koweycode.blogspot.com, Score: 59, Comments: 3 On Reddit: http://goo.gl/oBU0r Original: http://goo.gl/lnUCU * Review: Learn You a Haskell for Great Good! Domain: jerf.org, Score: 57, Comments: 15 On Reddit: http://goo.gl/BjJq7 Original: http://goo.gl/P7u3x * The Haskell Heap : Inside P4 Domain: blog.ezyang.com, Score: 37, Comments: 3 On Reddit: http://goo.gl/EoV5D Original: http://goo.gl/ropku * First-class modules for Haskell : Shields and Peyton Jones, 2001 :: PDF Domain: research.microsoft.com, Score: 27, Comments: 1 On Reddit: http://goo.gl/7renV Original: http://goo.gl/7lHV4 * Darcs hacking sprint 6 report Domain: blog.darcs.net, Score: 27, Comments: 13 On Reddit: http://goo.gl/ljO1O Original: http://goo.gl/xRr6r * Ugly memoization Domain: augustss.blogspot.com, Score: 25, Comments: 8 On Reddit: http://goo.gl/D6FoV Original: http://goo.gl/IUL1M * Monoids for Maybe Domain: byorgey.wordpress.com, Score: 23, Comments: 2 On Reddit: http://goo.gl/yVU7O Original: https://byorgey.wordpress.com/2011/04/18/monoids-for-maybe/ * Don't forget to think about GC flags when doing performance tuning Domain: stackoverflow.com, Score: 20, Comments: 3 On Reddit: http://goo.gl/6xzEj Original: http://goo.gl/Xwkro * Haskell videos on video.google.com, which shuts down for good on April 29th 2011 Domain: google.com, Score: 20, Comments: 5 On Reddit: http://goo.gl/MizlZ Original: http://goo.gl/CxnBK * Evaluation on the Haskell Heap Domain: blog.ezyang.com, Score: 20, Comments: 2 On Reddit: http://goo.gl/EX5aE Original: http://goo.gl/cU7Nt Top StackOverflow Questions * What are the primary theoretical difficulties with adding ML-style modules to Haskell? votes: 27, answers: 3 Read on SO: http://goo.gl/8An0y * Optimizing numerical array performance in Haskell votes: 25, answers: 1 Read on SO: http://goo.gl/ykzlV * lenses, fclabels, data-accessor - which library for structure access and mutation is better votes: 17, answers: 1 Read on SO: http://goo.gl/c74uO * In Haskell performing 'and' and 'or' for boolean functions votes: 15, answers: 5 Read on SO: http://goo.gl/0U5pI * Automatic memoizing in functional programming languages votes: 11, answers: 4 Read on SO: http://goo.gl/hg8Ei * Alternative implementations of Haskell's standard library type classes votes: 9, answers: 3 Read on SO: http://goo.gl/LDp9u * Scheme vs Haskell for an Introduction to Functional Programming? [migrated] votes: 8, answers: 0 Read on SO: http://goo.gl/lbeX3 * Writing loops for interactive IO: problems with do-notation and layout votes: 5, answers: 1 Read on SO: http://goo.gl/HVRrR * Python-"is"-like equality operator for Haskell/GHC votes: 5, answers: 4 Read on SO: http://goo.gl/7Z4mA * Optimising a Haskell XML parser votes: 5, answers: 1 Read on SO: http://goo.gl/fsqqw About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz

1 0

Good reads?
by Christopher Svanefalk 27 Apr '11

27 Apr '11

[I originally posted this over in haskell-beginners. However, since this list has a lot more traffic, and I am not sure how many people read both lists, I thought I would post here as well. I apologize for the doublepost! Just want to make sure I can get some replies from the great people here who might not read the beginners list] Hey all, I have mostly been brought in imperative/OOP languages. In connection with my college studies, however, I have taken great interest in the functional paradigm, and would very much like to dig deeper into it. I am currently reading through Peyton-Jones "Haskell: The Craft of Functional Programming" (2nd ed.), as well as a great paper published by one of my professors (http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html) However, what other works, in your opinions, should I look into to get a more complete understanding of functional programming? Thanks in advance! Chris

5 6