- Beginners - Haskell.org

Question about recursion
by Nadav Chernin 09 Nov '10

09 Nov '10

Hi, all I wrote function that delete elements from list by indexes: delIndexes::[Int]->[a]->[a] delIndexes [] list = list delIndexes _ [] = [] delIndexes indexes list = take x list ++ delIndexes ( map (\y->y-x-1) xs ) ( drop (x+1) list( where )x:xs)=sort indexes There is problem that in each step of recursion this function sort list of indexes ( in last line) How can I write this code that sorting will be executed only once (in first step)? Thank you, Nadav

2 1

ANNOUNCE: Haskell Communities and Activities Report (19th ed., November 2010)
by Janis Voigtländer 09 Nov '10

09 Nov '10

On behalf of all the contributors, I am pleased to announce that the Haskell Communities and Activities Report (19th edition, November 2010) is now available in PDF and HTML formats: http://haskell.org/communities/11-2010/report.pdf http://haskell.org/communities/11-2010/html/report.html Many thanks go to all the people that contributed to this report, both directly, by sending in descriptions, and indirectly, by doing all the interesting things that are reported. I hope you will find it as interesting a read as I did. If you have not encountered the Haskell Communities and Activities Reports before, you may like to know that the first of these reports was published in November 2001. Their goal is to improve the communication between the increasingly diverse groups, projects, and individuals working on, with, or inspired by Haskell. The idea behind these reports is simple: Every six months, a call goes out to all of you enjoying Haskell to contribute brief summaries of your own area of work. Many of you respond (eagerly, unprompted, and sometimes in time for the actual deadline ;-) to the call. The editor collects all the contributions into a single report and feeds that back to the community. When I try for the next update, six months from now, you might want to report on your own work, project, research area or group as well. So, please put the following into your diaries now: ---------------------------------------- End of April 2011: target deadline for contributions to the May 2011 edition of the HC&A Report ---------------------------------------- Unfortunately, many Haskellers working on interesting projects are so busy with their work that they seem to have lost the time to follow the Haskell related mailing lists and newsgroups, and have trouble even finding time to report on their work. If you are a member, user or friend of a project so burdened, please find someone willing to make time to report and ask them to "register" with the editor for a simple e-mail reminder in April (you could point me to them as well, and I can then politely ask if they want to contribute, but it might work better if you do the initial asking). Of course, they will still have to find the ten to fifteen minutes to draw up their report, but maybe we can increase our coverage of all that is going on in the community. Feel free to circulate this announcement further in order to reach people who might otherwise not see it. Enjoy! Janis Voigtlaender <hcar at haskell.org>

1 0

State Monads (and OpenGL)
by Tom Hobbs 08 Nov '10

08 Nov '10

Hi all, I have a program which implements Conway's Game Of Life. It even has an open GL UI which shockingly works. I've followed a tutorial (http://blog.mikael.johanssons.org/archive/2006/09/opengl-programming-in-has…) which tells how to get the open GL to animate, and according to my sysouts, that's working to. The problem I have comes with the fact that between every frame I want to evolve my world but I'm really struggling working out how to get the state stuff working. Here's a snippet of my main function; main = do world <- sequence (take (worldSize * worldSize) $ repeat rand) -- randomly generate a square world -- code snipped out displayCallback $= (display position world) -- display method which is called on every frame redraw mainLoop Here, world is a [Int] and represents my cells. The display function as referenced by "displayCallback" is the function that is called back to everytime the frame is redrawn. I also have another function which takes in a world, updates the state of the cells and the evolved world, thus; evolve :: [Int] -> [Int] I've been reading through (a lot of) tutorials on the state monad but I'm not any closer to working out how I make the call to display take some kind of updated world. I've also got the following code; type World = State [Int] evolveS :: World [Int] evolveS = do w <- get let w2 = evolve w put w2 return w2 Which I believe to be the correct code for wrapping my [Int] in the state monad but now I have two problems; 1) I don't know if it's correct 2) I don't know how to apply it, even if it is Can anyone offer any advice? Many thanks, Tom

2 2

editing a list
by Jonathan Phillips 07 Nov '10

07 Nov '10

I have a list (more precisely a string) which I'm trying to recurse through, editing sections as I come to it. It's obvious how to do it with a for loop, but I'm doing it all wrong in haskell, as this simple task is running mind-numbingly slowly. addOneNum cycles through each line, and when it gets to character 23, it calls changeNo, which edits the string. The problem is clearly the adding on to the end of the string, but the only other way I can see of doing it is writing the 'new string' backwards and then reverse it at the end. This looks like it would make the function even less legible than it already is though. addOneNum :: String -> String -> Integer -> String addOneNum x [] _ = x addOneNum x (y:ys) n = case n of 23 -> changeNo x (y:ys) n _ -> case y of '\n' -> addOneNum (x ++ [y]) ys 1 _ -> addOneNum (x ++ [y]) ys (n+1) changeNo :: String -> String -> Integer -> String changeNo v (w:x:y:z:xs) n = case length(show((read([w,x,y,z])::Integer) + 1)) of 0 -> addOneNum (v ++ " ") xs (n+4) 1 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ " ") xs (n+4) 2 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ " ") xs (n+4) 3 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ " ") xs (n+4) 4 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1)) xs (n+4) _ -> error "asdf" changeNo w _ n = error "changeNo error" Also, while I'm at it, it looks like I want to be using an as-pattern (or some C-style #define thing): changeNo v (w:x:y:z:xs) n = case length(s@(show((read([w,x,y,z])::Integer) + 1))) of 0 -> addOneNum (v ++ " ") xs (n+4) 1 -> addOneNum (v ++ s ++ " ") xs (n+4) 2 -> addOneNum (v ++ s ++ " ") xs (n+4) 3 -> addOneNum (v ++ s ++ " ") xs (n+4) 4 -> addOneNum (v ++ s) xs (n+4) _ -> error "asdf" but that gives me a 'not in scope' error. Any suggestions? Cheers, PhiJ

5 4

General primitive recursion
by Russ Abbott 06 Nov '10

06 Nov '10

Thanks Stephen, That looks like a nice set of slides. You're right that what I call the mapFn and the reduceFn could be combined into one function. Logically, though, I think it's more intuitive if they are separated. In addition, it seems important to allow for the possibility of having a function at the terminal point. For example, here's how I would define merge. merge xs ys = recursionEngine (\(xs, ys) -> null xs || null ys) (\(xs, ys) -> xs ++ ys) (:) (\(x:xs, y:ys) -> min x y) (\(x:xs, y:ys) -> if x <= y then (xs, y:ys) else (x:xs, ys)) (xs, ys) I'm not sure how to translate that into the genPR formulation. merge xs ys = genPR (\(xs, ys) -> null xs || null ys) (\(x:xs, y:ys) -> if x <= y then (xs, y:ys) else (x:xs, ys)) <There is no constant that goes here.> (\(x:xs, y:ys) merged -> (min x y) : merged) Besides the problem with the third argument, the fourth argument is awkward since it must take both heads, take their min, and then add them to the result of the recursive call. I'd prefer to take the heads and the min in a separate step as in the fourth argument to recursionEngine. *-- Russ * On Sat, Nov 6, 2010 at 2:10 AM, Stephen Tetley wrote: > > > Hello Russ > > Richard Kieburtz has a slightly smaller formulation of primitive > recursion on page 13 of these slides - the fold-like argument 'h' > doesn't appear to need a change of type: > > http://programatica.cs.pdx.edu/P/Programatica%20Logic1.pdf > > genPR :: (a -> Bool) -> (a -> a) -> c -> (a -> c -> c) -> a -> c > genPR p b g h x = if p x then g else h x (genPR p b g h (b x)) > > > -- factorial function: > fact :: Integer -> Integer > fact = genPR (==0) (subtract 1) 1 (*) > > Ignoring changes in argument order, the type of your recursionEngine > is one term and one type variable larger: > > recursionEngine :: (a -> Bool) -> (a -> c) -> (b -> c -> c) -> (a -> > b) -> (a -> a)-> a -> c > > Best wishes > > Stephen > > > >

1 0

Lifting infix functions in applicative style
by Bastian Erdnüß 06 Nov '10

06 Nov '10

When I want to lift an infix function into an applicative functor I use 'liftA2' -- I just call it 'up' for the sake of brevity. But I always have to add some parenthesis since I don't know how to tell Haskel that `up op` shall have the same fixity as `op` has. Is there a way to do that? Cheers, Bastian

2 2

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