November 2010 - Beginners

Modeling recursive data structs
by Nikolay Artamonov 06 Nov '10

06 Nov '10

Hi all! How can we model in Haskell three hypothetic data structures A, B, C which obey following conditions: 1. A is anything 2. B is list of A's 3. C is list of A's or B's or another C's So, for example, it would be possible to write something like: C [A, B [A, A], A, C [A, B [A]]]. I wrote this code: data Super = A | B [A] | C[Super] Not surprisingly, Haskell refused to accept subexpression `B[A]`, because "Not in scope: type constructor or class `A'". How to solve this problem? More "real" example of A, B and C: data Shape = Point Int Int | Polyline [Point] | Shape [Shape] Interestingly, if I replace Polyline [Point] to Polyline [Shape] then definition will be accepted. But what if I want *polylines* consists of *points*, not any *shapes*? Thank you! -- Nikolay Artamonov

3 2

Decomposing recursion
by Russ Abbott 05 Nov '10

05 Nov '10

As someone who comes into contact with Haskell only once a year when I teach an introductory Haskell course, I'm not familiar with whether the following is of any general interest. It struck me that one can decompose recursive functions into their pieces which can then be plugged into a recursion engine. Define a recursion engine as follows. recursionEngine termCond termFn reduceFn mapFn wayAheadFn = recursiveFn *where *recursiveFn y | termCond y = termFn y | *otherwise *= reduceFn (mapFn y) (recursiveFn (wayAheadFn y)) Then one can define, for example, factorial as follows. factorial = recursionEngine (==0) -- *termCond*. Stop when we reach 0 (\_ -> 1) -- *termFn*. At 0, return 1. (*) -- *reduceFn*. After the recursive call multiply n * factorial (n-1). id -- *mapFn*. This is what's saved for the reduce function. (+ (-1)) -- *wayAheadFn*. The recursive call is made on n-1. What I like about this is that it abstracts out the recursive process and allows one to plug functions into it to achieve what one wants. This is similar in spirit to map, foldr, and similar higher order functions. I'm writing because I like this and wanted to share it. Also, the standard higher order functions are, or course, widely used. My question is whether this has been pushed further to generate widely used libraries of other higher order functions and if so whether there is a discussion of them somewhere. In other words, what other algorithmic frameworks have been abstracted in this way? (I wouldn't count, for example, sort and zip since only one function is plugged into their abstract versions; changing that function doesn't significantly change the *kind *of computation being done.) Although it's hard to tell, I didn't see anything that looked similar in either the libraries that come with the standard Haskell download or on hackage <http://hackage.haskell.org/packages/archive/pkg-list.html>. This wiki page<http://cs.calstatela.edu/wiki/index.php/Courses/CS_332F/Recursion_engines>is my presentation of this. Besides a recursionEngine it also includes a tailRecursionEngine (for tail recursion, naturally) and an extendedRecursionEngine. The extendedRecursionEngine supports functions that require multiple recursive calls in the body such as mergesort or quicksort. Thanks. * -- Russ Abbott _____________________________________________* * Professor, Computer Science California State University, Los Angeles Google voice: 424-235-5752 (424-cell-rja) blog: http://russabbott.blogspot.com/ vita: http://sites.google.com/site/russabbott/ _____________________________________________*

2 1

Eliminate repetitive monad/list code
by John Smith 04 Nov '10

04 Nov '10

I have code which looks like this: foo :: IO A bar :: Bool -> A -> Int -> Bool -> IO () do x <- foo y <- foo z <- foo bar True x 1 False bar True y 2 False bar True z 3 False What is the best way to factor it, including eliminating the temporary x,y,z variables? I can get this down to foo :: IO A bar :: Bool -> A -> Int -> Bool -> IO () bar' a b = bar True a b False do x <- foo y <- foo z <- foo bar x 1 bar y 2 bar z 3 but I don't know what to do next. Is there some form of list comprehension or combination of map and lift which will eliminate the repetition?

3 3

Questions about lambda calculus
by Patrick LeBoutillier 04 Nov '10

04 Nov '10

Hi all, I've been reading this article: http://perl.plover.com/lambda/tpj.html in which the author talks about the lambda calculus and uses examples in Perl (here's a link directly to the code: http://perl.plover.com/lambda/lambda-brief.pl) I'm a total newbie with respect to the lambda calculus. fA = \x -> 'A' fB = \x -> 'B' x -=- y = (show $ x id) == (show $ y id) I tried (naively) to port these examples to Haskell to play a bit with them: fTRUE = \a -> \b -> a fFALSE = \a -> \b -> b fIF = \b -> \x -> \y -> b x y fPAIR = \a -> \b -> \f -> f a b fFIRST = \p -> p fTRUE fSECOND = \p -> p fFALSE fZERO = fPAIR fTRUE fTRUE fSUCC = \x -> fPAIR fFALSE x fIS_ZERO = \x -> fFIRST x fPRED = \x -> fSECOND x fONE = fSUCC fZERO fTWO = fSUCC fONE fADD = \m -> (\n -> fIF (fIS_ZERO m) n (fADD (fPRED m) (fSUCC n))) but I couldn't get fADD to compile: Occurs check: cannot construct the infinite type: t = (t1 -> t1 -> t1) -> t Probable cause: `fADD' is applied to too many arguments In the third argument of `fIF', namely `(fADD (fPRED m) (fSUCC n))' In the expression: fIF (fIS_ZERO m) n (fADD (fPRED m) (fSUCC n)) I think its because in these Perl examples all functions are treated as being of the same type (number or type of args doesn't matter), but this is not the case in Haskell. Is there any way to create code similar to this in Haskell? Thanks, Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

1 0

pred (succ n)
by ben 04 Nov '10

04 Nov '10

Hello, this question is somewhat similar to the one I've asked some hours ago: I would like to have a predecessor operator PRED for the untyped lambda calculus that has the property that PRED (SUCC n) --> n (I) for a suitable successor function SUCC. So far I've tried with SUCC := S := \nfx.f (n f x) and PRED := P := \nfx.n (\gh.h (g f)) (\u.x) (\u.u) for which I can prove beta equivalence P (S n) == n by induction on n, but not the property (I). Could anybody give me a pointer? Greetings, ben ps. Please keep me in CC, since I'm not currently subscribed to the list.

1 0

fixpoint operator for ULC with specific reduction property
by ben 04 Nov '10

04 Nov '10

Hello, I'm looking for a fixpoint operator Z for the untyped lambda calculus that has the property Z g --> g (Z g) for any g. The best-known fixpoint operator Y := \f. (\x. f (x x)) (\x. f (x x)) does not have this property, but only Y g --> T <-- g (Y g) for some T. Does anybody know such a Z I'm looking for? Greetings, ben ps. Please keep me in CC, since I'm not currently subscribed to the list.

2 2

Case statements shorter
by Angel Alonso 02 Nov '10

02 Nov '10

Hi, I have the following piece of code: n = 3 case n of 3 -> "Something" 4 -> "Something" _ -> "Other" Is it possible to shorten the case statement into something like this?: n = 3 case n of 3 or 4 -> "Something" _ -> "Other" Thanks. -- Angel Alonso

8 10

Re: [Haskell-beginners] Case statements shorter
by uu1101＠gmail.com 02 Nov '10

02 Nov '10

Nice distinction! Thank you for the correction. Il giorno 02/nov/2010, alle ore 09.11, Roel van Dijk <vandijk.roel(a)gmail.com > ha scritto: > On Mon, Nov 1, 2010 at 7:23 PM, uu1101(a)gmail.com <uu1101(a)gmail.com> > wrote: >> * _ is not a special keyword in haskell. It's a regular variable so >> will >> always match. It's usually used when you don't use it's value in >> the right >> hand side or when it adds no information. In this case its value >> will be n >> so there is no reason to introduce another name. > > This is incorrect. _ is a pattern not a variable. > > I can write > > f (_:_) = "bla" > > but not > > f (x:x) = "bla" > Conflicting definitions for `x' In the definition of `f' > > So _ is a pattern that always matches but is never bound to a value. > > Regards, > Roel

1 0

How to Install Gtk2Hs on Windows?
by John Smith 01 Nov '10

01 Nov '10

I tried following the directions on http://jystic.com/2010/10/20/installing-gtk2hs-on-windows/, but when I run cabal install gtk, I get * Missing C libraries: z, cairo * Missing C libraries: gobject-2.0, glib-2.0, intl I seem to have everything asked for in the PATH. pkg-config reports that Gtk+ 2.16.2 is installed.

1 1