Talk:Haskell/Recursion

From Wikibooks, the open-content textbooks collection

Contents 1 Too much recursion 2 Removed example 3 The exercise on (!!) 4 Operator Precedence 5 Replicate

[edit] Too much recursion

"A note on equation order

Unlike the other example, the order of the two recursive declarations is important. Haskell matches function calls starting at the top and picking the first one that matches. In this case, if we had the equation starting factorial n before the 'special case' starting factorial 0, then the general n would match anything passed into it, including, importantly, 0. So a call factorial 0 would match on the general, n case, the compiler would conclude that factorial 0 equals 0 * factorial -1, and so on to negative infinity. Not what we want."

Just a student's opinion: the compiler is not so mathematically well optimized in this particular situation, probably it would be wise to stop recursion in the case of multipling by 0, as the result of any more multiplication will be also 0. Maybe has this something with lazyness? - Gery Mate

But the compiler is doing exactly what you asked it to. The problem here is a mismap between intent and what one wrote: we intend to say that our factorial function is only defined on n >= 0, or the set of natural numbers, but what we wrote is that factorial is valid for all integers, positive and negative. This is an argument for either making this restriction explicit in the code, or better typing. I don't think Haskell has a "Natural" type though. --Gwern (contribs) 02:20, 15 February 2007 (UTC)

[edit] Removed example

I removed the following example from the "aside" section:

An example: sometimes you'll want to read input from the user that includes linebreaks/newlines. A looping solution would be to read a line of input, append it to a string variable containing all previous lines, check it for whatever marks the end of the input (ending the loop if true, or looping again if false). Here's a recursive solution which will accumulate input until the '.' is input:

To me, this seems too advanced to go at this point in the book. I suppose that's arguable, but at any rate I don't think the example adds all that much to the text at this point. It's a nice example, though, so I'm putting it here for someone else to do something with (which could of course include putting it back in a way that makes sense =).

--Byorgey 22:01, 4 July 2007 (UTC)

[edit] The exercise on (!!)

What should (!!) do when its first argument is the empty list? --GPhilip (talk) 08:38, 30 December 2007 (UTC)

The predefined (!!) in the Haskell Prelude raises an exception in that case.

 [] !! n = error "index too large"

-- apfeλmus 09:41, 30 December 2007 (UTC)

[edit] Operator Precedence

In the list concatenation example, the pattern-match recursive case is:

(x:xs) ++ ys = x : xs ++ ys

How come this isn't evaluated as "(x:xs) ++ ys" rather than the implicitly intended "x : (xs ++ ys)"? Doesn't Haskell evaluate from left to right?

Destynova (talk) 04:41, 12 February 2008 (UTC)

The right word is "operator precedence", the word "evaluation order" already has a different meaning. What happens here is similar to the well known fact that multiplication * binds tighter than addition +, so x + xs * ys parses as x + (xs * ys). For the precedence of the predefined operators from the Prelude, see also Fixity Declarations in the Haskell Report. You will note that ++ and : have the same precedence, but there's a second property called "fixity" which says whether x + y + z parses as (x + y) + z or as x + (y + z) or doesn't parse at all. Both ++ and : parse in the right-associative way and this explains what happens here.

-- apfeλmus 09:38, 12 February 2008 (UTC)

[edit] Replicate

In this chapter in the excercises, there is an excercise to make a 'replicate' function. However, if you define this in your haskell file and load it into GHCi, GHCi becomes confused if you mean the Prelude-build-in replicate or your own replicate function from the excercise, and starts complaining about ambiguity. Therefore, I renamed 'replicate' to 'replicat'. Feel free to rename to a better solution. --H.Kwint 82.170.165.133 (talk) 02:06, 7 March 2009 (UTC)