0

現在Functional Programming in Scalaの日本語訳を読んでいます。exercise 4.5のtraverse関数を実装せよという問題に関しての質問です。

def traverse[A,B](as:List[A])(f:A=>Option[B]):Option[List[B]]= as match{
 | case Nil => Some(Nil)
 | case (h::t) => for{
 | hh <- f(h)
 | tt <- traverse(t)(f)
 | } yield(hh::tt)
 | }

 traverse: [A, B](as: List[A])(f: A => Option[B])Option[List[B]]

この関数は正常に動くようですが、

traverse((1 to 10000).toList)(i => Some(i))

と長さが一万程度のlistでstackoverflowになってしまいます。
flatMap内で再帰しているので末尾再帰にできません。
flatMapで再帰する関数でstacksafeにするにはどのようにすればいいでしょうか。

2 件の回答 2

2

この本のGitHubにあるヒントと答えを見ると、foldRighttraverseを実装できるよ、と書いてあります(答えを先に見るのが嫌な人は、1つめのリンクだけクリックしてください)。

https://github.com/fpinscala/fpinscala/blob/master/answerkey/errorhandling/05.hint.txt
https://github.com/fpinscala/fpinscala/blob/master/answerkey/errorhandling/05.answer.scala

ここで、第3章のエクササイズを一通りやっていれば、List.foldRightを末尾再帰に実装する方法も出てきたはずです。その方法で実装されているfoldRightを使えば、traverseもスタックセーフに実装できると思います。(Scala標準のListもfoldRightは末尾再帰で実装されているようなので、多分そのままでスタックセーフに動くのではないでしょうか。)

2
1

方法はいくつかあるかもしれませんが、とりあえずScalazではDList(差分リスト)を使っています

https://github.com/scalaz/scalaz/blob/v7.1.1/core/src/main/scala/scalaz/std/List.scala#L44-L60

1
  • scalazすごいけど難しいですね。。 traverseのように '>>= ' , 'flatMap' 内から再帰する場合 スタックセーフにするためには モナド共通の解決法のようなものはなくてそれぞれに対応するという事なんでしょうか このscalazの実装も [github.com/fpinscala/fpinscala/blob/master/answerkey/… のfoldrを使った実装と原理は一緒でしょうか
    – tim
    2015年4月3日 5:09

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。