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は本当に無限リストになっているようだ。

タグ ：
#haskell