📈Haskellの無限リストを完遂せよ
[10, 14..]infinite listでいいみたいだ。Lazy Listとも呼ばれるらしい
Lispの例だと思うがここに解説が
実際にはアクセスに必要な分だけストリームを計算しているにもかかわらず、ストリームを完全な実体として操作するという錯覚をサポートする方法を見てきました。この技術を利用して，たとえシーケンスが非常に長い場合でも，シーケンスをストリームとして効率的に表現することができます．さらに驚くべきことに，ストリームを使って無限に長いシーケンスを表現することができます．
この本の原本のようだ。
関数型言語においては専ら、無限の大きさ（長さ、要素数）の再帰的なデータ構造を指す。遅延評価を用いて実装されるため「遅延ストリーム」とも呼ばれる。無限のデータを扱うには、そのうちの一部を切り出したりする関数も必要なほか、ストリームを成すデータも再帰関数によって生成されるため、オブジェクト指向の関数型言語では、これらをまとめてストリームクラスとして実装することもある。関数が出力するストリーム自体は連結リストとして実装されることが多い。
遅延評価は必要なときに必要なだけ関数を評価し、不要になったら関数の評価を正常に中断することができる。このことは再帰呼び出しを中断する条件（停止条件）の判定を一切行わない再帰関数や再帰的な値の定義を可能にする。たとえば階乗を求める関数は、1から順に再帰的にかけ算してその結果を返すよう定義するだけである。上限などを設ける必要はなく、かわりに「結果をn個求めてリストにする」関数や「結果をx個捨てる」関数などを介して呼び出す。条件判定をしないということは、遅延評価を行わない言語では無限ループに陥いるということである。
わかりづら
Scheme言語やその他の言語では、ストリームとはデータ要素の遅延評価や遅延シーケンスのことを指します。ストリームはリストと似たような使い方ができますが、後の要素は必要な時だけ計算されます。したがって、ストリームは無限の系列や系列を表すことができます。
Smalltalk標準ライブラリや他のプログラミング言語でも、ストリームは外部イテレータです。Scheme と同様に、ストリームは有限または無限のシーケンスを表すことができます。
ストリームは、遅延リストと呼ばれることもありますが、要求に応じてのみ計算される要素を含むシーケンシャルなデータ構造です。ストリームは、nullか、またはcdr内のストリームとのペアです。ストリームの要素はアクセスされたときにのみ計算されるため、ストリームは無限大になることがあります。一度計算されたストリーム要素の値は、再び必要になった場合に備えてキャッシュされます。
メモ機能を持たないストリームは、1965年にPeter Landinによって初めて記述されました。メモ化は、約10年後にストリームの本質的な機能として受け入れられるようになりました。今日では、ストリームはHaskellのような関数型プログラミング言語のシグネチャデータ型となっています。
Rosetta様にも少しあった
zklの例
w:=mergeStreams([0..],[2..*,2],[3..*,3],T(5));
w.walk(20).println();Racketの例
#lang lazy
(define nats (cons 1 (map add1 nats)))
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l))
(define (sieve l) (cons (first l) (sieve (sift (first l) (rest l)))))
(define primes (sieve (rest nats)))
(!! (take 25 primes))誰得なんだ、これ
やっと来た本命Haskellの例
[0]から始まる長さが増加するRecaman配列の無限系列を定義し，それらを単純に検索して，長さ15の最初の系列，または重複する整数を含む最初の系列を見つけることができます．3番目の課題では，[0...1000]を部分集合として含む最初のものが見つかるまで，サイズが大きくなるRecaman生成の整数集合の無限の流れを検索すれば十分です．
Recamán's sequence[1][2]（またはRecaman's sequence）は、再帰関係で定義されたよく知られた配列であり、その要素が前の要素と素直に関連していることから、再帰を用いて定義されることが多い。
いいなと思ったら応援しよう！
