「nを1から初めてその２乗を足していき、和が2000を初めて超えたとき和はいくつになるかという問題」をScalaで解いてみた

なんか凄い長いタイトルだ。元ネタはプログラミング言語が与える影響 (GrayRecord)

とりあえず、NyaRuRuさんのC#版の解

結局 C# 版はこんなコードになりました．

using System;
using System.Collections.Generic;
using System.Linq;

using Achiral;
using Achiral.Extension;

static class Program
{
    static void Main(string[] args)
    {
        var seq =
            1.UpToInfinity()                                 // [1, 2, 3, 4, ...]
             .Select(x => x * x)                             // [1, 4, 9, 16, ...]
             .Scan((sum, x) => sum + x)                      // [1, 5, 14, 30, ...]
             .TakeWhile((sum, _, __) => sum <= 2000,         // 2000 を超えるまで
                        (_, __, subIndex) => subIndex < 1);  // 次に，最初の要素まで

        Console.WriteLine("answer: {0}", seq.Last());
    }
}

http://d.hatena.ne.jp/NyaRuRu/20080527/p1

をできるだけ忠実にエミュレーションすることを目標に書いてみた。Scalaだとこのような無限リストを扱うにはStreamを使う(Iteratorでもできなくは無いけど、色々めんどう)。ただ、Scanに相当するメソッドがScalaには無いので、そこはimplicit conversionで追加してみた。

import Stream._
implicit def enrichStream[A](s: Stream[A]) = new {
  def scan[B >: A](f: (B, A) => B): Stream[B] = {
    def g(acc: B, s: Stream[A]): Stream[B] = {
      s match {
        case cons(hd, tl) => val n = f(acc, hd); cons(n, g(n, tl))
        case empty => empty
      }
    }
    val cons(hd, tl) = s
    g(hd, tl)
  }
}
println(from(1).map(x => x * x).scan(_+_).dropWhile(_ <= 2000).head)

こういう高階関数を使ったメソッドチェインが続くとき、implicit anonymous functionを使うと気持ち良く書けることが多い気がする。

追記：

NyaRuRuさんの日記より：

nsharp さんのコメントにあるように，SkipWhile + First の組み合わせは，そもそも Enumerable.First の述語を取る版で OK なのでした……

http://d.hatena.ne.jp/NyaRuRu/20080527/p1

なるほど。Scalaならfindを使ってこんな感じだろうか。

println(from(1).map(x => x * x).scan(_+_).find(_ > 2000).get)