Haskellで同じ要素がつづく無限リストはこんな感じで書ける。
import Debug.Trace cons x xs | trace("cons") False = x:xs cons x xs = x:xs inf1 = 1 : inf1 inf2 = cons 1 inf2 inf3 x = cons x (inf3 x)
で、実際のデータ構造はどうつくられるのか? ひとつはこれ↓
___________ ___________ ___________ | | | | | | | | | inf -->| | ----->| | ----->| | ----->... |__|__|_____| |__|__|_____| |__|__|_____| | | | |_______________|_______________| | V 1
もうひとつはこれ↓
+-------------+ | | V__________ | | | | | inf -->| | -----+ |__|__|_____| | V 1
やってみた。
% ghci foo.hs GHCi, version 7.0.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Loading package ffi-1.0 ... linking ... done. [1 of 1] Compiling Main ( foo.hs, interpreted ) Ok, modules loaded: Main. *Main> take 3 inf1 [1,1,1] *Main> take 3 inf2 cons [1,1,1] *Main> take 3 (inf3 1) cons [1cons ,1cons ,1] *Main>
というわけで、inf1とinf2は自己参照ループになっている方で、inf3は本当に無限リストになっているようだ。