ハスケルで有限リストを連結した無限リストの最後のアイテムを取得するには？

Question

Haskellでは、有限リストを連結した無限リストの最後のアイテムを効率的に取得する方法を教えてください。

lastは動作しません。頭から、それは明らかに反復し、以下が終了したことがないので：

-- 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：私は[1..] ++ [0]のHaskellの内部表現であるのだろうか、それは完全に「最初にあるの未評価 "？ 内部でが2つの（評価されていない）リストの "シーケンス"のように表す場合、last関数は最後の項目の最後の項目をただちに取得できます。

Answer 1

追加操作++の内部表現が何であっても、それは言語定義に適合しなければなりません。

Haskell 2010 Language Report specifies：

(++) :: [a] -> [a] -> [a]

アペンド二つのリスト、すなわち、

[x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn] 
    [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...] 

最初のリストが有限でない場合、結果は最初のリストです。

はい、あなたは

last (xs ++ ys) == last ys 

の法律を取得することを目指し、特定の方法で headまたは lastなどのさまざまな要求に応答し、その引数リストを保持するメモリにいくつかの善意のオブジェクトのように、別々にそれを定義しようとすることができ

を保持する。それはハスケルではない。 Haskellでは

Answer 2

一般的には、任意の式に対して、“ハスケルの内部表現”を見つけることはできません。ハスケル標準は、そのようなことを内部表現として定義していない。それを選択するのはコンパイラの責任です。

実施例では、[1..] ++ [0]は、2つの異なるリストを指すサンクとして十分に表されることになる。しかし、結果が飛び散る要素が何個であっても、常に最初の無限リスト（標準はを保証します）から引き継いでいます。したがって、コンパイラは++ [0]を完全に完全に自由に最適化することができます。なぜなら、結果には全く影響を及ぼし得ないからです。

おそらく無限の長さの複数のリストを格納し、それらのうちの1つ以上のヘッドにアクセスする必要がある場合は、明示的にしてください。例えば、ネストされたリスト[[1..], [0]]を使用するだけです。

Answer 3

リストは左バイアスされ、リストの最後の要素を取得するために、あなたは全体の背骨を横断する必要がありますが、lists defined as free monoids公平であり、したがって

last $ fromList [1..] `append` fromList [0] 

0に計算しますので。しかし、そのようなリストは独自のproblemsを持っています。