名古屋Scala練習場

4種類のアルファベット "A,C,G,T" から成るn文字の文字列のうち、"AAG"という並びが含まれる文字列を全て列挙するプログラムを書きなさい。ただし、nは3以上の整数とし、文字列内に同じアルファベットが出現しても構わないものとし、出力順序は問わないものとします。

... 適性検査に合格された方はその生産性を実現可能な方です。生産性に見合う初任給として年俸1000万円をご用意しております。

Haskellだと4行。

permutation :: [a] -> Int -> [[a]]
permutation xs n = sequence $ take n $ repeat xs

solve :: Int -> [String]
solve n = filter (isInfixOf "AAG") $ permutation ['A', 'C', 'G', 'T'] n

上のScalaバージョン

object Main {
  def main(_args: Array[String]) = {
    solve(5) |> (s => println(s))
  }

  def repeat[A](x : A) : Stream[A] = x #:: repeat(x)

  def permutation[A](xs : List[A], n : Int) : List[List[A]] = {
    repeat(xs).take(n).toList |> ListMonad.sequence
  }

  def solve(n : Int) : List[String] = {
    permutation(List('A', 'C', 'G', 'T'), n).map(_.mkString).filter(_.contains("AAG"))
  }

  trait Monad[M[_]] {
    def mbind[A,B](m : M[A])(f : A => M[B]): M[B]
    def mret[A](x : A): M[A]
    def sequence[A](ms : List[M[A]]) : M[List[A]] =
      ms match {
        case Nil => mret(Nil)
        case m::ms =>
          mbind(m) {
            x => mbind(sequence(ms)) {
              xs => mret(x::xs)
            }
          }
      }
  }

  object ListMonad extends Monad[List] {
    override def mbind[A,B](m:List[A])(f: A => List[B]) = m.flatMap(f)
    override def mret[A](x : A) = List(x)
  }

  implicit def AofT[T](x: T) : {def |>[S](f:T=>S): S} = new { def |>[S] (f: T => S): S = f(x) }
}

F#で解いた方もいらっしゃいました。
http://twitter.com/#!/katayama_k/status/156688925463818240
http://www4.atwiki.jp/fsharpmaster/pages/24.html

PHPで普通に書くと17行でしたhttps://gist.github.com/1604840