8702


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

[code]

    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]]
    
[/code]

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

[code]

    traverse((1 to 10000).toList)(i => Some(i))
    
[/code]

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


CC BY-SA 3.0
2015-04-02T09:29:02.783
8688
2015-04-03T00:17:48.063
8928
question
scala
flatMap内での再帰呼び出しの最適化


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

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


CC BY-SA 3.0
2015-04-02T09:50:00.723
8689
2015-04-02T09:50:00.723
56
8688
answer


この本のGitHubにあるヒントと答えを見ると、`foldRight`で`traverse`を実装できるよ、と書いてあります（答えを先に見るのが嫌な人は、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`は末尾再帰で実装されているようなので、多分そのままでスタックセーフに動くのではないでしょうか。）


CC BY-SA 3.0
2015-04-02T18:00:27.600
8702
2015-04-03T00:17:48.063
2015-04-03T00:17:48.063
244
244
8688
answer