を実装してみました。
過去にも
- 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
````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