How to get last items of infinite list concatenated with finite list in Haskell?
In Haskell, how to efficiently get the last item(s) of an infinite list concatenated with a finite list?
last does not work, it obviously iterates from the head, so the following never finishes:
-- let's have a list of all natural numbers,
-- with zero appended
arr = [1..] ++ [0]
-- it was fast! now get the last item, should be easy
res = last arr
EDIT : I wonder what is the Haskell's internal representation of [1..] ++ [0] , is it initially "totally unevaluated"? If it would internally represent it like a "sequence" of two (unevaluated) lists, the last function could just get the last item of the last item, immediately.
Whatever the internal representation of an append operation ++ is, it has to conform to the language definition.
Haskell 2010 Language Report specifies:
(++) :: [a] -> [a] -> [a]
Append two lists, ie,
[x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
[x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
If the first list is not finite, the result is the first list.
Yes, you could try to define it differently, like some bona fide object in memory holding its argument lists, responding to different requests like head or last in specific ways, aiming to get the law of
last (xs ++ ys) == last ys
to hold; but that is just not Haskell.
You can't in general find “Haskell's internal representation” for any expression. The Haskell standard defines no such thing as an internal representation; it's up to the compiler to choose one.
In a naïve implementation, [1..] ++ [0] would sure enough be represented as a thunk pointing to two different lists. However, no matter how many elements you pop off the result, you will always take from the first, infinite list (the standard does guarantee that). So the compiler is perfectly free to optimise the ++ [0] away altogether, because it can provenly make no difference to the outcome.
If you actually need to store multiple lists of possibly infinite length and access the head of more than one of them, well, make it explicit! For instance just use a nested list [[1..], [0]] .
Lists in Haskell are left-biased, so in order to get the last element of a list you have to traverse the whole spine, but lists defined as free monoids are unbiased and hence
last $ fromList [1..] `append` fromList [0]
computes to 0 . But such lists have their own problems.
上一篇: F＃开发和单元测试？