<div>Thanks Richard and the others who responded to my query.</div>
<div> </div>
<div>I truly appreciate you taking the time and effort to respond to me (and the community) with your thoughts.</div>
<div> </div>
<div>I had been reading about recursion, and was thinking only of that approach to solve this.</div>
<div> </div>
<div>My main reson for looking into Haskell is because I am intruiged that Haskell does not allow side effects. I have literally seen code (not my own, of course!) that is nothing but side effects, and over time such code becomes very expensive to maintain and extend. I wonder if functional programming may be the paradigm of the future just because it is in the longer run cost effective.</div>
<div> </div>
<div>Anyway, thanks again, and Best Regards</div>
<div> </div>
<div>Chris Tauss<br></div>
<div class="gmail_quote">On Mon, Sep 20, 2010 at 6:11 PM, Richard O'Keefe <span dir="ltr"><<a href="mailto:ok@cs.otago.ac.nz">ok@cs.otago.ac.nz</a>></span> wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">
<div>
<div></div>
<div class="h5"><br>On Sep 18, 2010, at 7:51 PM, Christopher Tauss wrote:<br><br>> Hello Haskell Community -<br>><br>> I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements.<br>
><br>> There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept.<br>><br>> Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like<br>
> n_lastn 3 = [3,4,5]<br>><br>> Seems like it would be something like:<br>><br>> n_lastn:: [a]->Int->[a]<br>> n_lastn 1 (xs) = last(xs)<br>> n_lastn n (x:xs) = ????<br>><br>> The issue is I do not see how you can store the last elements of the list.<br>
<br></div></div>Part of the reason why you may be having trouble is that you are thinking<br>about things like "how you can store the last elements of the list". I'm<br>having trouble imagining what that might mean.<br>
<br>Let's look at this in completely abstract terms.<br>A list is a sequence.<br>A (finite) sequence has a length, and there is a length function to find it.<br>We can split a sequence into pieces, and there are take and drop functions<br>
to do it.<br>We have these building blocks:<br><br> length :: [t] -> Int --length of sequence<br> take :: Int -> [t] -> [t] --first n elements<br> drop :: Int -> [t] -> [t] --all BUT the first n elements<br>
<br>The only one of these that gives us a suffix of a list is 'drop'.<br>So we are going to need<br><br> n_lastn :: Int -> [t] -> [t]<br> n_lastn count list = drop ???? list<br><br>What is the first argument of drop going to be?<br>
drop wants the number to DISCARD.<br>You have the number to KEEP.<br>The number to discard + the number to keep is the total length.<br>So you will discard (length list - count) elements.<br>And here we go with a complete answer:<br>
<br> n_lastn count list = drop (length list - count) list<br><br>This is a mathematical definition about (finite) sequences.<br>We could write it and reason about it even if there had never been<br>any such thing as a computer. It doesn't actually matter in the<br>
least HOW a list is stored; this definition will be RIGHT.<br><br>Whether it is *efficient* does depend on how a list is stored.<br>There are questions like<br> - how often does the sequence have to be traversed<br> (with lists, determining the length involves walking along<br>
the whole list until the end is found, although it does not<br> involve looking at the elements)<br> - how much copying is done<br> (with arrays, you'd have to make a new array of count elements<br> and copy the last count elements of list to it, with lists you<br>
don't have to copy anything)<br><br>I can make this point another way. n_lastn is a bad name, because<br>really, it's just the same as `take` except working from the other<br>end. So we can define<br><br> reverse_take n = reverse . take n . reverse<br>
reverse_drop n = reverse . drop n . reverse<br><br>"the last n items of a sequence are the first n items of its reversal, reversed"<br>"all but the last n items of a sequence are all but the first n<br>
items of its reversal, reversed"<br><br>and your n_lastn is just reverse_take. This definition does three list<br>traversals and two copies.<br><br>There's a trick I found very useful in Prolog, and that is to exploit<br>
the homomorphism between lists and natural numbers, where a list can be<br>used to represent its own length.<br><br>Let's take `take` and `drop`.<br><br> take (n+1) (x:xs) = x : take n xs<br> take _ _ = []<br>
<br> drop (n+1) (_:xs) = drop n xs<br> drop _ xs = xs<br><br>Instead of passing a natural number as first argument, we'll pass<br>a list, and the analogue of (n+1) is then (_:k).<br><br> list_take, list_drop :: [any] -> [t] -> [t]<br>
<br> list_take (_:k) (x:xs) = x : list_take k xs<br> list_take _ _ = []<br><br> list_drop (_:k) (_:xs) = list_drop k xs<br> list_drop _ xs = xs<br><br>(drop count list) is a list, whose length is the number of elements we<br>
want to discard from the beginning of list. So we can define<br><br> reverse_take count list = list_drop (drop count list) list<br><br>and this does O(length list) work; ONE list traversal and NO copies.<br><br> reverse_drop count list = list_take (drop count list) list<br>
<br>This code was tested thus:<br>*Main> [reverse_take n "abcd" | n <- [0..4]]<br>["","d","cd","bcd","abcd"]<br>*Main> [reverse_drop n "abcd" | n <- [0..4]]<br>
["abcd","abc","ab","a",""]<br><br><br></blockquote></div><br>