Swiftで無限リスト

を実装してみました。

• https://github.com/dankogai/swift-lazylist

過去にも

• Perl http://blog.livedoor.jp/dankogai/archives/50839189.html
• JavaScript https://github.com/dankogai/js-list-lazy

などでも実装していて、我ながらどれだけ Lazy List が好きなんだと思いますが、 Swiftのそれは格別に気持ちいいです。

以下、READMEから。

Infinite list

let ns = lazylist { $0 } // infinite list of natural numbers
println(ns.filter{$0 % 2 == 1}.map{$0 * $0}.take(10)) // [1, 9, 25, 49, 81, 121, 169, 225, 289, 361]
println(ns.map{$0 * $0}.filter{$0 % 2 == 1}.take(10)) // [1, 9, 25, 49, 81, 121, 169, 225, 289, 361]

Finite list

let a100 = lazylist(Array(0..<100)) // [0, 1, 2 ... 99]
println(a100.drop(10).take(10))   // [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
println(a100.drop(90).take(20))   // [90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -- only 10
println(a100.drop(100).take(10))  // [] -- no elements left

Infinite list with seed array

let fibs = lazylist([0,1]){ i, a in a[i-2] + a[i-1] }
println(fibs.drop(10).take(10)) // [55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] -- F10...F19

let primes = lazylist([2,3]) { i, ps in
    for var n = ps[i-1] + 1; true; n++ {
        for p in ps {
            if n % p == 0 { break }
            if p * p > n  { return n }
        }
    }
}
println(primes.take(25)) // first 25 prime numbers -- primes less than 100

考え方は、過去の Lazy Lists の実装同様、「要素がなければ作ってしまえばいいじゃない!」というものですが、今回は「あってもなくても作ってしまえ」モードが追加されています。それが、上記の自然数の例。自然数を作るのに元になる配列は不要ですよね?

この場合のメモリー効率は、HaskellやRubyを上回ります。たとえば、以下の例ではどちらも一時的に1,000,000,010個の要素の配列を作ってしまうためだんまりになってしまうのですが…

Haskell

take 10 $ drop 1000000000 [0..]

Ruby

(0..Float::INFINITY).lazy.drop(1_000_000_000).take(10)

以下は瞬殺です。

lazylist{ $0 }.drop(1_000_000_000).take(10)

どうやっているかはソースを参照のこと。

Enjoy!

Dan the Lazy Lister