2

Haskell が無限リストを実現する方法について頭を悩ませようとしています...ここに私の障害があります:

type のリストがあり、型クラスAをA実装していOrdます。順序付けられた要素のスパンを次のように記述できます (たとえば、整数):

[1..6]

これは...に相当します

Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 (Cons 6 (Empty))))))

haskell はどのようにして無限リストを構築する方法を知っているのでしょうか? Haskell は、サポートするデータ型の無限リストを作成できますOrdか?

4

3 に答える 3

6

Haskell は、必要になるまで要素を作成しないため、無限リストを「作成」します。たとえば、厳密な言語で Haskell と無限ループがhead [1..]発生する展開を見てみましょう。1

head [1..]

===                                 [expand `head`, literally 
                                     just inline the definition]
case [1..] of
  []        -> error "empty list"
  (x : xs)  -> x

===                                 [evaluate [1..] one step,
                                     check if it matches the case]
case 1:[2..] of
  []        -> error "empty list"
  (x : xs)  -> x

===                                 [it does!]

(1 : [2..]) -> 1

===                                 [fin]

1

これは、 を攻撃する[1..]代わりにの定義を攻撃することから始まるほとんどの言語と比較して、かなり後方にあることに注意してくださいhead。

[x..]型クラス内の任意の型Ord(2 つのものが互いに大きいか小さいかのみを示すことができます) ではなく、代わりに型クラス内の任意のものをEnumwhere に変換[x..]して記述できます。enumFrom xenumFrom :: Enum a => a -> [a]

于 2013-07-25T21:30:02.093 に答える
4

[a..b]構文的に甘いものから離れて、プレリュードからの単純な関数について考える方が少し簡単かもしれません:

repeat :: a -> [a]
repeat x = x : repeat x

ここでは評価のことは忘れて、宣言的に考え始める必要があります。つまり、上記を、読み取り可能な数学の関数のように考えてください。

"repeat x" は、"repeat x" を含む "x" を意味します。

はい、「遅延評価」とは、これを表現できるようにするものですが、理想的には、評価を忘れて、コードが何を意味するかを考えたいと思います。命令型プログラミングでは、常に評価について考える必要があります。

これは多かれ少なかれあなたの脱糖するもの[1..]です：

enumFrom n = n : enumFrom (succ n)

@telの回答で、コンパイラがそれをどのように拡張するかを見ることができます。

于 2013-07-25T23:50:53.470 に答える