[Haskell-beginners] Haskell Question

[Seph Shewell Brockway]

On Fri, Oct 18, 2019 at 06:59:05PM +0200, Ut Primum wrote:
> Hi,
> this is my solution:
> 
> productLastPart :: Int -> [Int] -> Int
> productLastPart n xs = product (take n (reverse xs))
> 
> It only uses functions product, take and reverse
> Regards,
> Ut

That should work. I’d probably use point-free style, though, and avoid
all of those brackets.

   productLastPart n = product . take n . reverse

The version you’ve written runs in linear time, as would a version that
worked like this:

   productLastPart n xs = product (drop (length xs - n) xs)

because reverse, length and product (actually a partial application of
foldr) are all linear in the length of the list—they access each element
once. You can see the GHC implementation of reverse at
https://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.List.html#reverse.
This turns out to be the best we can do with a regular Haskell list,
because accessing the last element of a list is a linear-time operation:

   last :: [a] -> a
   last [] = error "Oh no!"
   last [x] = x
   last (x : xs) = last xs

There do, however, exist list types like Sequence and Vector that allow
constant-time access to both ends of the list.

Hope this is helpful.

                                                Seph

-- 
Seph Shewell Brockway, BSc MSc (Glas.)
Pronouns: she/her