読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

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

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)