[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
x
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