2

クラスのために書くためのScala の演習での関数型プログラミングでの私の試みは次のとおりです。toListStream

def toList[A](stream: Stream[A]): List[A] = {
    def go(s: Stream[A], acc: List[A]): List[A] = s match {
        case x #:: xs => go(xs, acc :+ x)
        case _ => acc
    }
    go(stream, Nil)
}

この投稿を読んだ (ただし、すべてを理解しているわけではない) に基づいて、パターン マッチングが正しいかどうか確信が持てませんでした。特に、最初のケースでは、ストリームの末尾をすぐに評価する結果になっていることが懸念されました。

概念的には、各ステップのテールを評価するのではなくtoList、各再帰ステップがストリームのヘッドをリストに追加する場所を実装する必要があると思います。

この理解と上記の実装は正しいですか?

4

1 に答える 1

4

docs と source は、Streamこれにかなりうまく対応しています。

のソース#::は次のとおりです。

  object #:: {
    def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] =
      if (xs.isEmpty) None
      else Some((xs.head, xs.tail))
  }

これに関連する部分はSome((xs.head, xs.tail)). ソースには次のようにtail記載されています。

このメソッドは の評価を強制するのではStreamなく、遅延した結果を返すだけであることに注意してください。

docs に基づいてxs、 case ステートメントで評価されませんcase x #:: xs。このケースが一致する場合、 thengo(xs, acc :+ x)が呼び出されます。xsこれは基本的s.tailに、上記のように評価されません。

リンク先の投稿のコードは、 tail( a Stream) の再帰呼び出しで使用され、mergeその後unapply呼び出されて頭と尾に分解されるという点で異なります。headは であるため、Stream評価され、十分な大きさの入力でオーバーフローがスタックされます。@Didier Dupontもこれをうまく述べています：

また、Scala Stream では、テールはレイジーですが、ヘッドはそうではないことに注意してください。(空でない) ストリームがある場合、ヘッドを認識している必要があります。つまり、ストリームの末尾、それ自体がストリーム、つまり元のストリームの 2 番目の要素であるその先頭を計算する必要があることを意味します。これは時々問題になりますが、あなたの例では、そこにたどり着く前に失敗します。

コード内のheadとtailfor の抽出では、 が. つまり、ストリームのストリームです。他の投稿のコードは、再帰呼び出しを介してこの状況を作成します。xsAStreammerge

于 2013-11-04T05:48:59.100 に答える