S25

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P25 (*) Generate a random permutation of the elements of a list.
// Hint: Use the solution of problem P23.
// Example:
// scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
// res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f)

// P20 (*) Remove the Kth element from a list.
def removeAt[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): (List[T], T) = (i, xs) match {
    case (0, h :: t) => (acc.reverse ::: t, h)
    case (i, h :: t) => r(i - 1, t, h :: acc)
  }
  if(i < 0 || xs.size <= i) throw new NoSuchElementException else r(i, xs, Nil)
}

import scala.util.Random
def randomPermute[T](xs: List[T]) = {
  val rand = new Random
  def r(ys: List[T], acc: List[T]): List[T] = {
    if(ys.size == 1) ys.head :: acc
    else {
      val (rest, removed) = removeAt(rand.nextInt(ys.size), ys)
      r(rest, removed :: acc)
    }
  }
  if(xs.isEmpty) Nil else r(xs, Nil)
}

解答例
またもや、してやられたぜ！

S24

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P24 (*) Lotto: Draw N different random numbers from the set 1..M.
// Example:
// scala> lotto(6, 49)
// res0: List[Int] = List(23, 1, 17, 33, 21, 37)

import scala.util.Random
def lotto(n: Int, to: Int) = {
  val rand = new Random()
  def r(acc: List[Int]): List[Int] = {
    def next(): Int = {
      val i = rand.nextInt(to)
      if(acc.count(_ == i) == 0) i else next
    }
    if(acc.size < n) r(next :: acc) else acc
  }
  if(n < 1 || to < n) throw new IllegalArgumentException
  else r(Nil)
}

解答例
こりゃ一本とられたわい

S23

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P23 (**) Extract a given number of randomly selected elements from a list.
// Example:
// scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
// res0: List[Symbol] = List('e, 'd, 'a)

import scala.util.Random

// P20 (*) Remove the Kth element from a list.
def removeAtR[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): (List[T], T) = (i, xs) match {
    case (0, h :: t) => (acc.reverse ::: t, h)
    case (i, h :: t) => r(i - 1, t, h :: acc)
  }
  if(i < 0 || xs.size <= i) throw new NoSuchElementException else r(i, xs, Nil)
}

def randomSelect[T](n: Int, xs: List[T]) = {
  val rand = new Random()
  def r(ys: List[T], acc: List[T]): List[T] = {
    val (rest, removed) = removeAtR(rand.nextInt(ys.size), ys)
    if(n <= acc.size + 1) removed :: acc
    else r(rest, removed :: acc)
  }
  if(n <= 0 || xs.size < n) throw new IllegalArgumentException
  else r(xs, Nil)
}

解答例
君のは違うけど、わしのは末尾再帰だよ。

Scalaでいい感じにtap

最近のRubyにある、超便利メソッドtapの使い方のメモ。
Scalaでimplicit conversionを使ったtapの実装はScala で tap メソッドを使う - Rainy Day Codingsに書いてある。

メソッドチェーンを切らずにtapしてprintlnとかよくやるけど、今日はそれ以外の使い方を学んだ。うはは。

tapを使わない場合は気の毒で目も当てられない

import java.util.Properties
def loadProperties(path: String): Properties = {
  val p = new Properties()
  p.load(new FileInputStream(new File(path).getAbsolutePath))
  p
}

オブジェクト作って呼び出し元に返したいが、
初期化メソッドの戻り値がthisじゃないからローカル変数に一度入れてからreturnしなきゃならんっていう古いjavaライブラリによくあるケース。

tapを使うとローカル変数がいらなくなる

import java.util.Properties
def loadProperties(path: String): Properties = {
  new Properties().tap( _.load(new FileInputStream(new File(path).getAbsolutePath)))
}

いいねぇ！

S22

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P22 (*) Create a list containing all integers within a given range.
//  Example:
// scala> range(4, 9)
// res0: List[Int] = List(4, 5, 6, 7, 8, 9)

def rangeTail(from: Int, to: Int) = {
  def r(current: Int, acc: List[Int]): List[Int] = {
    if(current <= to) r(current + 1, current :: acc)
    else acc.reverse
  }
  r(from, Nil)
}

def rangeBuiltin(from: Int, to: Int) = List.range(from, to + 1).toList

解答例
unfoldRightっていう発想はなかった。 だけど、末尾再帰じゃないじゃないか。 これじゃすぐstackoverflowだ。 ということで、unfoldRightの末尾再帰版を書いてみた。

def unfoldRightTail[A, B](s: B)(f: B => Option[(A, B)]): List[A] = {
  def recursive(s: B, acc: List[A]): List[A] = {
    f(s) match {
      case None         => acc.reverse
      case Some((r, n)) => recursive(n, r :: acc)
    }
  }
  recursive(s, Nil)
}
def rangeFunctionalTail(start: Int, end: Int): List[Int] =
  unfoldRightTail(start) { n =>
    if (n > end) None
    else Some((n, n + 1))
  }

scalaでstructural typingでreflection

Scala: How do I dynamically instantiate an object and invoke a method using reflection?

にstructural typingを使ったサンプルが載ってたのでメモ

class Foo {
  def hello(name: String): String = "Hello there, %s".format(name)
}

object FooMain {

  def main(args: Array[String]) {
    val foo  = Class.forName("Foo").newInstance.asInstanceOf[{ def hello(name: String): String }]
    println(foo.hello("Walter")) // prints "Hello there, Walter"
  }
}

S21

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P21 (*) Insert an element at a given position into a list.
// Example:
// scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
// res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)

def insertAt[T](e :T, n: Int, xs: List[T]) = {
  def r(n: Int, rest: List[T], acc: List[T]): List[T] = (n, rest) match {
    case (0, h :: t) => acc.reverse ::: List(e) ::: rest
    case (_, h :: t) => r(n - 1, t, h :: acc)
  }
  if(n < 0 || xs.size <= n) throw new NoSuchElementException else r(n, xs, Nil)
}

def insertAt2[T](e :T, n: Int, xs: List[T]) = {
  if(n < 0 || xs.size <= n) throw new NoSuchElementException
  val splitted = xs.splitAt(n)
  splitted._1 ::: List(e) :::  splitted._2
}

解答例
君、それ好きだよね。

S20

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P20 (*) Remove the Kth element from a list.
// Return the list and the removed element in a Tuple. Elements are numbered from 0.
// Example:
// scala> removeAt(1, List('a, 'b, 'c, 'd))
// res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)

def removeAt[T](i: Int, xs: List[T]) =
  if(i < 0 || xs.size <= i) throw new NoSuchElementException
  else (xs.zipWithIndex.filter{_._2 != i}.map{_._1}, xs(i))

def removeAtR[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): (List[T], T) = (i, xs) match {
    case (0, h :: t) => (acc.reverse ::: t, h)
    case (i, h :: t) => r(i - 1, t, h :: acc)
  }
  if(i < 0 || xs.size <= i) throw new NoSuchElementException else r(i, xs, Nil)
}

解答例の上のやつ、いいね。

scalaでactor使ってparallel map その3 - Futures編

その1
その2
でparallel mapの実装を試みたところActorの理解が浅く、実はシングルスレッドだったという衝撃の事実が発覚して度肝を抜かれた。

めげずに、Using scala actor framework as fork-join computation?とかScalaActors.pdf
を参考にしてFuturesを使って実装してみた。

今回は、 FuturesをListの要素数分作って、mapでFuturesをapplyする場合と、
Futuresの数を制御したい場合の2パターンを実装してみた。

import scala.actors.Future
import scala.actors.Futures._

import java.util.concurrent._

trait Pmap {

  // FuturesをListの要素数分作る場合
  def pmap[T, U](xs: List[T])(fun: T => U): List[U] = {
    val mapfuncs = xs.map{ x => future { fun(x) } }
    mapfuncs.map{ _() }
  }

  // for Debug
  def pmap_debug[T, U](xs: List[T])(fun: T => U): List[U] = {
    val mapfuncs = xs.map{ x => future {
        println("start Thread " + currentThread.getId)
        val r = fun(x)
        println("end Thread " + currentThread.getId)
        r
    } }
    mapfuncs.map{ _() }
  }

  // Futuresの数を制限したい場合
  def pmap[T, U](xs: List[T], n: Int)(fun: T => U): List[U] = {
    val mapfuncs = divide(n, xs).map{ l =>
      future { l.map( fun(_) ) }
    }
    mapfuncs.flatMap{ _() }
  }

  // for Debug
  def pmap_debug[T, U](xs: List[T], n: Int)(fun: T => U): List[U] = {
    val mapfuncs = divide(n, xs).map{ l =>
      future {
        println("start Thread " + currentThread.getId)
        val result = l.map( fun(_) )
        println("end Thread " + currentThread.getId)
        result
      }
    }
    mapfuncs.flatMap{ _() }
  }

  def divide[T](n: Int, xs: List[T]): List[List[T]] = {
    val size = xs.size / n
    def r(ys: List[T], acc: List[List[T]]): List[List[T]] = {
      if(ys.size < size) (acc.head ::: ys) :: acc.tail
      else{
        val splitted = ys.splitAt(size)
        r(splitted._2, splitted._1 :: acc)
      }
    }
    r(xs, Nil).reverse
  }
}

object Main extends Application with Pmap {

  val l: List[Int] = (1 to 100000).toList
  pmap[Int, Int](l, 4)(x => x + 1)
  pmap_debug[Int, Int](l, 2)(x => x + 1)
  pmap[Int, Int](l)(x => x + 1)
  pmap_debug[Int, Int](l)(x => x + 1)
}

pmap_debugを実行すると

start Thread 13
start Thread 11
start Thread 12
start Thread 10
end Thread 10
end Thread 11
end Thread 12
end Thread 13

と出るのでマルチスレッドで非同期に実行されていることが確認できた。

Futures10万個の場合では実際に（2コア2スレッドのマシンでは）4スレッドで切り盛りしていた。
（環境依存。4コア8スレッドのマシン上では合計16スレッドだった）

2コア2スレッドマシン
% sort /tmp/output.txt |uniq -d
end Thread 10
end Thread 11
end Thread 12
end Thread 13
start Thread 10
start Thread 11
start Thread 12
start Thread 13

どっちがよいかは場合によるだろう。

リストの数がそれほど大きくなくて、mapにそこそこ時間がかかる場合を考えてみる。
リストをまず分割して、その断片にFuturesを割り当てる方式だと、
分割したリスト断片間を処理する時間にばらつきがあると、一番遅い断片の処理時間に引っ張られそう。
リストの要素ごとにFuturesを作った方が処理時間が平準化されてトータルでは早くなりそうだ。

今回のようにリストの数が膨大だとFuturesの数を抑えたが方が、高速でメモリにもやさしそうだ。

リストの要素数、mapの処理内容、CPUコア数によって変わるだろうから実際に動かして決めるのが良さそうだな。

scalaでactor使ってparallel map その2

-----------
これもシングルスレッドだ。パラレルじゃない。Futureを使わないFork-Joinは再チャレンジする（11/8追記）
----------

前回の実装はイケてない。
pmapの関数定義の結果型がList[Any]（実際はList[List[T]]）だった。
map的にはList[T]を返した方が自然だよな。

ということで改良してみた。

import scala.actors.Actor._

@SuppressWarnings(Array("unchecked"))
def pmap[T, U](xs: List[T], n: Int)(fun: T => U): List[U] = {

  def divide(n: Int, xs: List[T]): List[List[T]] = {
    val size = xs.size / n
    def r(ys: List[T], acc: List[List[T]]): List[List[T]] = {
      if(ys.size < size) (acc.head ::: ys) :: acc.tail
      else{
        val splitted = ys.splitAt(size)
        r(splitted._2, splitted._1 :: acc)
      }
    }
    r(xs, Nil).reverse
  }

  val mapped: List[List[U]]  = divide(n, xs).map{ l =>
    val a = actor { receive { case _ => reply(l.map(fun(_))) } }
    a !? "s" match {
      case l: List[U] => l
      case _ => Nil
    }
  }

  mapped.flatten
}

val l = (1 to 100).toList
val result = pmap[Int, Int](l, 4)(_ + 1)

println(result)

実行すると、

warning: non variable type-argument U in type pattern List[U] is unchecked since it is eliminated by erasure
case l: List[U] => l
^
one warning found
List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101)

となる。

erasureによって型Uが消されてるからcase List[U]がU以外でもマッチしてあぶねーよ、っていわれてる。
@SuppressWarnings(Array("unchecked"))書いても警告がでるのね。
無視スリゃいいんだろうけど気持ち悪い。

scalaでactor使ってparallel map その3 - Futures編に続く。

scalaでactor使ってparallel map その1

-----------
これ、シングルスレッドだ。パラレルじゃない。Futureを使わないFork-Joinは再チャレンジする（11/8追記）
----------

試しに書いてみた。

pmapの結果型がList[T]だと型チェックエラーでコンパイルできない。
replyすると型情報が消えちまうのか？

パラレルマップの正解はこれとかこれかもしれない。
また今度試す。

import scala.actors.Actor._

def pmap[T](xs: List[T], n: Int)(fun: T => T): List[Any] = {

  def divide(n: Int, xs: List[T]): List[List[T]] = {
    val size = xs.size / n
    def r(ys: List[T], acc: List[List[T]]): List[List[T]] = {
      if(ys.size < size) (acc.head ::: ys) :: acc.tail
      else{
        val splitted = ys.splitAt(size)
        r(splitted._2, splitted._1 :: acc)
      }
    }
    r(xs, Nil).reverse
  }

  divide(n, xs).map{ l =>
    val a = actor { receive { case _ => reply(l.map(fun(_))) } }
    a !? "s"
  }
}

val l = (1 to 100).toList
val result = pmap(l, 4)(_ + 1)

println(result)

実行結果

List(List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26), List(27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51), List(52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101))

scalaでactor使ってparallel map その2に続く。

S19

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P19 (**) Rotate a list N places to the left.
// Examples:
// scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)
// scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)

def rotate[T](i: Int, xs: List[T]) = {
  val splitted = xs.splitAt(i)
  splitted._2 ::: splitted._1
}

// match - case version
def rotateR[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): List[T] = (i, xs) match {
    case (_, h :: t) if 0 < i => r(i - 1, t, h :: acc) //tail recursion
    case (0, rest) => rest ::: acc.reverse // Only 1 time.
  }
  if(i < 0 || xs.size <= i) xs else r(i, xs, Nil)
}

// if version
def rotateRIf[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): List[T] = {
    if (0 < i) r(i -1, xs.tail, xs.head :: acc ) //tail recursion
    else xs ::: acc.reverse // only 1 time.
  }
  if(i < 0 || xs.size <= i) xs else r(i, xs, Nil)
}

val l = (1 to 1000000) toList

println(rotate(999999, l)) // ok
println(rotateR(999999, l)) // ok
println(rotateRIf(999999, l)) // ok

解答例
へそ曲がりめ！

S18

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P18 (**) Extract a slice from a list.
// Given two indices, I and K, the slice is the list containing the elements from and including the Ith element up to but not including the Kth element of the original list. Start counting the elements with 0.
// Example:
// scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: List[Symbol] = List('d, 'e, 'f, 'g)

def sliceBuiltin[T](i: Int, k: Int, xs: List[T]) = xs.slice(i, k)

def slice[T](i: Int, k: Int, xs: List[T]) = xs.drop(i).take(k - i)

def sliceZip[T](i: Int, k: Int, xs: List[T]) =
  xs.zipWithIndex.filter(x => i <= x._2).filter(x => x._2 < k).map(_._1)

def sliceFoldL[T](i: Int, k: Int, xs: List[T]) =
  xs.foldLeft((0, List[T]()))((acc, x) =>
    if(i <= acc._1 && acc._1 < k) (acc._1 + 1, x :: acc._2)
    else (acc._1 + 1, acc._2)
  )._2.reverse

def sliceRecursiveNotTail[T](i: Int, k: Int, xs: List[T]): List[T] = (i, k, xs) match {
  case (_, _, Nil)  => Nil
  case (0, _, h :: tail) if(0 < k) => h :: sliceRecursiveNotTail(0, k - 1, tail)
  case (_, _, _ :: tail) if(0 < i)  => sliceRecursiveNotTail(i - 1, k - 1, tail)
  case (_, 0, _) => Nil
}

def sliceRecursiveTail[T](i: Int, k: Int, xs: List[T]) = {
  def recursive(i: Int, k: Int, xs: List[T], acc: List[T]): List[T] =
    (i, k, xs) match {
      case (_, _, Nil)  => acc
      case (0, _, h :: tail) if(0 < k) => recursive(0, k - 1, tail, h :: acc)
      case (_, _, _ :: tail) if(0 < i)  => recursive(i - 1, k - 1, tail, acc)
      case (0, 0, _) => acc
    }
  recursive(i, k, xs, Nil).reverse
}

val l = (1 to 1000000) toList

//println(slice(1, 110000, l))
//println(sliceZip(1, 110000, l))
//println(sliceFoldL(1, 110000, l))
println(sliceRecursiveNotTail(1, 110000, l)) // StackOverFlow
//println(sliceRecursiveTail(1, 110000, l))

解答例
似たようなケースがある場合は、if文で書いた方がすっきりすることもあるのね。

S17

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P17 (*) Split a list into two parts.
// The length of the first part is given. Use a Tuple for your result.
// Example:
// scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))

// tail revursion but too slow
def split_tail_too_slow[T](nth: Int, xs: List[T]) = {
  def recursive(n: Int, rest: List[T], acc: (List[T], List[T])): (List[T], List[T]) = rest match {
    case Nil => throw new NoSuchElementException
    case l if (n == 0) => (acc._1, l)
    case h :: t => recursive(n - 1, t, (acc._1 ::: List(h), Nil)) // add to tail -> O(n)
  }
  if(nth <= 0) throw new IllegalArgumentException else recursive(nth, xs, (Nil, Nil))
}

// tail revursion
def split_tail_fast[T](nth: Int, xs: List[T]) = {
  def recursive(n: Int, rest: List[T], acc: (List[T], List[T])): (List[T], List[T]) = rest match {
    case Nil => throw new NoSuchElementException
    case l if (n == 0) => (acc._1.reverse, l)
    case h :: t => recursive(n - 1, t, (List(h) ::: acc._1 , Nil)) // add to head -> O(1)

  }
  if(nth <= 0) throw new IllegalArgumentException else recursive(nth, xs, (Nil, Nil))
}

def split_take[T](nth: Int, xs: List[T]): (List[T], List[T]) =
  (xs.take(nth) , xs.takeRight(xs.length - nth))

val l = (1 to 1000000).toList
println(split_take(100000, l))
println(split_tail_fast(100000, l))
println(split_tail_too_slow(100000, l)) // 超遅い

３方式で書いてみた。

split_tail_too_slowはリストの最後尾に追加する。追加の度にリストをたどらなければならないので、再帰の度に遅くなる。O(n)
split_tail_fastはリストの先頭に追加するため、リストの要素数に関係なくO(1)
split_tail_takeはList APIを使ったバージョン。


100万個のリストで(10万, 90万)で分割（split_take以外の2つは10万回再帰）してみたところ、
split_tail_too_slowはいつまでたっても終わらなかった。

末尾再帰にすりゃいいってもんじゃないのね。勉強になりました。

解答例
ふむふむ、splitAtってのがあるのね。
match式にタプルを使えばいいのか。if式がいらなくなるのね。なるほど。

S16

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P16 (**) Drop every Nth element from a list.
// Example:
// scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)

// not tail recursive version
def drop_nottail[T](n: Int, xs: List[T]): List[T] = xs match {
  case h :: t if (n == 1) => drop_nottail(n - 1, t)
  case h :: t => h :: drop_nottail(n - 1, t)
  case Nil => xs
}

// tail recursive version
def drop_tail[T](nth: Int, xs: List[T]) = {
  def recursive[T](n: Int, tail: List[T], acc: List[T]): List[T] = tail match {
    case h :: t if (n == 1) => recursive(n - 1, t, acc)
    case h :: t => recursive(n - 1, t, h :: acc)
    case Nil => acc
  }
  recursive(nth, xs, Nil).reverse
}

// zipwithindex version
def drop_zipWithIndex[T](nth: Int, xs: List[T]) = {
  xs.zipWithIndex.flatMap{
    case (_, i) if (i + 1 == nth) => Nil // drop nth
    case (e, _) => e :: Nil
  }
}

val l: List[Int] = (1 to 100000).toList
//println(drop_nottail(3, l)) // StackOverflowError
//println(drop_tail(3, l))
println(drop_zipWithIndex(3, l))

解答例
そうまでして1行で書きたいってか！！

S15

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向だけど、List要素の増殖は以前書いたので今回はList.fillを使った。

// P15 (**) Duplicate the elements of a list a given number of times.
//     Example:
//     scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))
//     res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)

def duplicateN[T](n: Int, xs: List[T]): List[T] = xs match {
  case Nil => xs
  case h :: t => List.fill(n)(h) ::: duplicateN(n, t)
}

def duplicateN_tail[T](n: Int, xs: List[T]) = {
  def recursive[T](n: Int, tail: List[T], acc: List[T]): List[T] = tail match {
    case Nil => acc
    case h :: t => recursive(n, t, List.fill(n)(h) ::: acc)
  }
  recursive(n, xs, Nil).reverse
}

def duplicateN_map[T](n: Int, xs: List[T]) = xs.flatMap(List.fill(n)(_))

val l = List('a, 'b, 'c, 'c, 'd)
println(duplicateN_tail(100000, l))
println(duplicateN_map(100000, l))
println(duplicateN(100000, l))  // 末尾再帰じゃないはずだが、stackoverflowにならないのが不思議

解答例
やっぱりそうきますか。

S14

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向で。

// P14 (*) Duplicate the elements of a list.
// Example:
// scala> duplicate(List('a, 'b, 'c, 'c, 'd))
// res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)

def duplicate[T](xs: List[T]): List[T] = xs match {
  case h :: t => h :: h :: duplicate(t)
  case Nil => xs
}

def duplicate_tail[T](xs: List[T]) = {
  def recursive(ys: List[T], acc: List[T]): List[T] = ys match {
    case Nil => acc
    case h :: t => recursive(t, h :: h :: acc)
  }
  recursive(xs, Nil).reverse
}

def duplicate_map[T](xs: List[T]): List[T] = xs.flatMap{ x => x :: x :: Nil}

//val l = List('a, 'b, 'c, 'c, 'd)
val l = 1 to 1000000 toList

println(duplicate_tail(l))
println(duplicate_map(l))
println(duplicate(l)) // StackOverFlow

解答例
そうですよね。

scala + ctags + vim + taglistできた

scalaの開発環境改善中。

まずは、ctagsをscalaに対応させる方法を見て、関数定義にタグジャンプできるようにした。

その後、taglist.vimを使ってみたのが、そのままではタグの一覧が表示されなかったのでググってみたらドンピシャな記事を発見。

Has anyone got the vim taglist plugin working with Scala?

↑に書いてあるとおり、taglist.vimの、

s:tlist_def_yacc_settings

の後ろに↓の2行追加したらできました。

let s:tlist_def_scala_settings = 'scala;t:trait;c:class;T:type;' .
\ 'm:method;C:constant;l:local;p:package;o:object'

ちなみに、タグジャンプ等のキーバインドは、
Vimの極め方　tags-and-searchesを使い易くする
この設定がシックリきてます。

S12

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向で。

//P12 (**) Decode a run-length encoded list.
//Given a run-length code list generated as specified in problem P10, construct its uncompressed version.
//Example:
//scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
//res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)

def decode[T](xs: List[(Int, T)]) = {

  // not tail recursion
  def ntimes_nottail(n: Int, x: T): List[T] = {
    if (n < 0) throw new IllegalArgumentException
    else if (n == 0) Nil
    else x :: ntimes_nottail(n - 1, x)
  }

  // tail recursion
  def ntimes_tail(ntimes: Int, x: T) = {
    def ntimes_rec(n: Int, result: List[T]): List[T] = {
      if (n == 0) result else ntimes_rec(n - 1, x :: result)
    }
    if (ntimes < 0) throw new IllegalArgumentException else ntimes_rec(ntimes, Nil)
  }

  // tail recursion
  def recursive(ys: List[(Int, T)], result: List[T]): List[T] = ys match {
    case Nil => result
    case (times, x) :: tail =>  recursive(tail, result ::: ntimes_tail(times, x))
//    case (times, x) :: tail =>  recursive(tail, result ::: ntimes_nottail(times, x))
  }

  recursive(xs, Nil)
}


val l = List((5, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))
println(decode(l))

末尾再帰版（ntimes_tail）だと100万回のループでもStackOverFlowにならなかったが、
非末尾再帰版だと10万回でStackOverFlowした。

解答例
そ、そんな！！

vimからsbtを実行できた

ここに、scalaのakkaプロジェクト創始者のjboner君のvimrcがあったので、これは！！と思って覗いてみたら、vimからsimple-build-toolを使う部分があったので、試してみた。

ちょっとハマったのでメモしておく。

"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" For SBT
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
set makeprg=sbt-no-color\ test-compile
...省略...
set errorformat=%E[error]\ %f:%l:\ %m,%C[error]\ %p^,%-C%.%#,%Z,
\%W[warn]\ %f:%l:\ %m,%C[warn]\ %p^,%-C%.%#,%Z,
\%-G%.%#

となっている。

sbt-no-colorってなんぞや思いつつも、.vimrcにコピって:makeしてみたけど、sbt-no-colorがないと怒られる。

そこで、sbt-no-colorをsbtに変更して:makeすると、sbtでコンパイルしてるようなんだけど、
[0m[...のように文字化けてる風味で出力される。

:!sbt test-compile 2>&1| tee /tmp/vQCb1aG/2
[0m[ [0minfo [0m] [0mBuilding project test 1.0 against Scala 2.8.0 [0m
...省略...
[0m[ [32msuccess [0m] [0mBuild completed successfully. [0m

15分位ググっても引っかからん。うーんうーん唸っていたら僕ちゃん、気づきました。

「色」だ。　no-colorだ。

ということで。sbtのソース落としてgrep "color" **/*.scalaとかやったら出てきた。
in Logger.scala

private val formatEnabled = ansiSupported && !formatExplicitlyDisabled
private[this] def formatExplicitlyDisabled = java.lang.Boolean.getBoolean("sbt.log.noformat")

sbtを起動するシェルスクリプトを↓のように書き換え、

java -Dsbt.log.noformat=true -Xmx512M -jar /path_to_/sbt-launch-0.7.4.jar "$@"

sbt-no-colorという名前で保存後、jboner君のvimrcで、:makeでvim上からsbt使ってコンパイルすることができました。

---------
ちなみに、gvim上でエラー行にマークするには、
errormarker.vimがいいよ。

vimでscalaをomni補完するプラグイン codefellowが動かん

vimでscalaのomni補完ができるという
codefellow
を試したけど、1時間イジって動かなかったので諦めた。。
scalaのファイルを開くと固まる。

screeencast見たらすごすぎておったまげた。
ぜひ使わせてもらいたかったんだがなー。


もう少し時が満ちてから試す。
備忘録としてメモっとく。

scalaでDir.glob("**/*.sql")

RubyだとDir.glob("**/*.sql")で指定したディレクトリから、
再帰的に*.sqlのファイルパスを検索してくれるが、
scalaには見当たらなかったので、書いてみた。

  // glob **/*.sql 
  val globSqlFiles = glob((f: File) => 
    !f.isDirectory && f.getName.endsWith(".sql")) _
  
  // curried function
  def glob(filter: (File) => Boolean)(dirs: List[String]): List[File] = {
    def recursive(dir: File, acc: List[File]): List[File] = 
      Option(dir.listFiles) match {
        case None => throw new FileNotFoundException(dir.getAbsolutePath)
        case Some(lists) => 
          val filtered = lists.filter{ c =>  filter(c) }.toList
          val childDirs = lists.filter{ c => c.isDirectory && !c.getName.startsWith(".") }
          return ( (acc ::: filtered) /: childDirs){ (a, dir) => recursive(dir, a)}
    }
    dirs.flatMap{ d => recursive(new File(d), Nil)}
  }

  // 使い方。対象ディレクトリはListで複数指定できる。
  globSqlFiles(List("/tmp/sql"))

汎用的になるようにカリー化してみた。
３、4行目の条件に正規表現を組み込めば曖昧検索できる。

S-99: Ninety-Nine Scala Problemsを頑張ってやっているせいか、
immutableなListの再帰に対してアレルギーがなくなってきた。

S10, S11

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向で。

// P10 (*) Run-length encoding of a list.
// Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E.
// Example:
// scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))

def pack[A](ls: List[A]): List[List[A]] = {
  if (ls.isEmpty) List(List())
  else {
    val (packed, next) = ls span { _ == ls.head }
    if (next == Nil) List(packed)
    else{
      packed :: pack(next)
    }
  }
}
def encode[T](xs: List[T]) = {
  pack(xs).map{ (x) => (x.length, x.head) }
}

def encodeModified[T](xs: List[T]) = {
  pack(xs).map{ (x) => if(x.length == 1) x.head else (x.length, x.head) }
}

解答例
同じだ。

S09

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向で。

// P09 (**) Pack consecutive duplicates of list elements into sublists.
// If a list contains repeated elements they should be placed in separate sublists.
// Example:
// scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

// tail recursion
def reverse[T](xs: List[T]): List[T] = {
  def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {
    case Nil => result
    case h :: t => recursive(t, h :: result)
  }
  recursive(xs, Nil)
}

// tail recursion
def removeLast[T](xs: List[T]): List[T] = {
  def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {
    case Nil => throw new NoSuchElementException
    case h :: Nil => result
    case h :: t => recursive(t, h :: result)
  }
  reverse(recursive(xs, Nil))
}

// tail recursion
def pack[T](xs: List[T]): List[List[T]] = {
  def recursive(rest: List[T], acc: List[List[T]]): List[List[T]] = {
    rest match {
      case Nil => acc
      case h :: t if(acc != Nil && h == acc.last.head) => 
        val nextAcc = List(h :: acc.last) //List[Listt[T]]
        recursive(t, removeLast(acc) ++ nextAcc) // List[List[T]] ++ List[List[T]] => List[List[T]]
      case h :: t =>
        val nextAcc = acc ++ List(List(h))
        recursive(t, nextAcc)
    }
  }
  recursive(xs, Nil)
}

val l = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
println(pack(l)) //=>  List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

解答例
spanっすか。