[Haskell-cafe] Need help of explanation possible!!! Pls

Albert Y. C. Lai trebla at vex.net
Sat Feb 24 14:10:39 EST 2007

iliali16 wrote:
> take :: Integer -> [Integer] -> [Integer] take _ [] = [] take n xs 
> |x < lenghtList xs = (take (n-1) xs :[]) |otherwise = xs I have 
> decleared lenghtList before.

The wrong expression "xs:[]" indicates a major misunderstanding; it 
worries me alot because you also say you understand well. This makes 
help nearly impossible because if I go back to the basic, which is 
exactly what is needed, you think you can skip it.

When you're given a list, there are two cases, as you know. One fits the 
pattern [], and your code has successfully caught that. The other fits 
the pattern x:s, the x being the first element of the list and the s 
being the remaining list. I'll say more because I have a point to make. 
For example if the given list is [3,1,4], and you match it against the 
pattern x:xs, then x refers to 3 and xs refers to [1,4]. The point I 
want to make is that x refers to 3, not [3], that x refers to the 
number, not a sublist; s does refer to a sublist.

Turn it around, if you have a number 3 and a list of numbers [1,4], you 
can put them together, 3 first, with 3:[1,4]. That will give you 
[3,1,4]. Again, the point is that it is not [3]:[1,4], that's wrong; it 
is 3:[1,4]. Therefore things like [2,1]:[7,5] and [1,4]:[] are also 
wrong. (What if you really want to put together [2,1] and [7,5]? There 
is a way, but it's off-topic today.)

Now I can talk about take. If the list is too short, you already handle 
that, so I just assume the list is long enough, e.g., "take 2 
[3,1,4,7]". There is a recursion here, but it's largely on n, not so 
much on the list. The base case is "take 0 blahblah", and no matter what 
blahblah happens to be, and no matter how long blahblah is, no one 
cares, the correct answer is [].

   take 0 _ = []

The inductive case is when n is non-zero, and since I can assume the 
list is long enough (you already have code for the short case), I can 
just assume it matches the pattern x:s (in fact you also already have 
code for the [] case). It is possible to apply the pattern x:s to 
"decompose" the list and still have the name xs refer to the whole list; 
it looks like

   take n xs@(x:s) | n < lengthList xs = ...

If the list is [3,1,4,7], then xs is still [3,1,4,7], x is 3, s is 
[1,4,7]. What can you do with these data?

You want to extract the first n guys. You can extract the first guy, that is


then use recursion to extract n-1 more guys, but skipping x, that is n-1 
guys from s but not xs:

   take (n-1) s

then you put them together, x first, that is

   x : take (n-1) s

The whole line of code looks like

   take n xs@(x:s) | n < lengthList xs = x : take (n-1) s

If you call "take 2 [3,1,4,7]", n is 2, x is 3, s is [1,4,7], you get

    take 2 [3,1,4,7]
-> 3 : take (2-1) [1,4,7]     we trust in recursion
-> 3 : [1]
=  [3,1]

Eventually someone will tell you that the test "n < lengthList xs" is 
unnecessary and, moreover, slows things down tremendously (not just 
slightly). Eventually someone will also tell you "what if n is 
negative", and you have to make a decision about that. They are right. 
But I will call it a day.

More information about the Haskell-Cafe mailing list