2016-07-29

Scala 関数型デザイン&プログラミング:Exercize3.16-3.23

日記 Scala 勉強

Scala 関数型デザイン&プログラミング:Exercize3.2 - 3.13 - 謎言語使いの徒然の続き。

Exercise 3.16

各要素に +1 したリストを返す関数を作れ。

なんか仕様的に map 関数に似てるなーと思った。
とりあえずフォイ

  def map[A, B](as: List[A], func: A => B): List[B] =
    foldRight(as, Nil:List[B])((a, b) => Cons(func(a), b))

  def increment(as: List[Int]): List[Int] = map[Int, Int](as, v => v + 1)

  /*  printRec(List.increment(List(1, 2, 3, 4))) */

Exercise 3.17

List[Double] を List[String] にする関数を作りなさい。

はいはい mapmap

  def toStringList[A](as: List[A]): List[String] = map[A, String](as, _.toString)

しかしこの map 型指定しないとコンパイルコケるのはダサいな。

Exercise 3.18

下記シグネチャで map 作れ def map[A, B](as: List[A], func: A => B): List[B]

上記 map のシグネチャだけ変更。
何か型推論がいい仕事始めて、「map[A, String](as, _.toString)」が「map(as)( _.toString)」になった。

引数が一つであることを（curry にでもして）保証すると精度でも上がるのかね？

Exercise 3.19

与えられた条件を満たされるまでリストから要素を削除する filter 関数を記述せよ。 def filter[A](as: List[A])(f: A => Boolean): List[A]

まぁ foldRight あれば余裕な

  def filter[A](as: List[A])(f: A => Boolean): List[A] =
    foldRight(as, Nil: List[A])((a, b) => if (f(a)) Cons(a, b) else b)
  /* printRec(List.filter(List(1,2,3,4,5,6,7,8,9))(_ % 2 == 0)) */

Exercise3.20

map と似た動きをする関数、flatMap を作れ。シグネチャは下記の通り。 def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] flatMap(List(1, 2, 3))(i => List(i, i)) と書いたら、List(1, 1, 2, 2, 3, 3) を返せ。

Scala 標準の flatMap ほど高機能ではないか…？

  def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] = concat(map(as)(f))
  /* printRec(List.flatMap(List(1, 2, 3))(a => List(a, a))) */

Exercise3.21

flatMap を使って filter を実装せよ。

何だ？ f(x)==false の時 Nil にでもするのか？

  def filterViaFlatMap[A](as: List[A])(f: A => Boolean): List[A] =
    flatMap(as)(a => if(f(a)) List(a) else Nil: List[A])

  /* printRec(List.filterViaFlatMap(List(1,2,3,4,5))(_ % 2 == 0)) */

何だろう…効率的な実装に見えない。

Exercise3.22

同数二つの List[Int] を受け取って、対応する要素同士で足し算する関数を作れ。

  def addPairwise(list: List[Int], list1: List[Int]): List[Int] = {
    def addPairwise(a: List[Int], b: List[Int], sum: List[Int]): List[Int] = {
      (a, b) match {
        case (Nil, _) => sum
        case (_, Nil) => sum
        case (Cons(ah, at), Cons(bh, bt)) => addPairwise(at, bt, Cons(ah + bh, sum))
      }
    }

    reverse(addPairwise(list, list1, Nil: List[Int]))
  }
  /* printRec(List.addPairwise(List(1,2,3), List(1,2,3))) */

こうですか？わかりません。

Exercise3.23

Exercise3.22 の処理を、加算、減算にとらわれずに実行できるようにせよ。

  def zipWith[A, B, C](al: List[A], bl: List[B])(f: (A, B) => C): List[C] = {
    def zipWith(a: List[A], b: List[B], r: List[C]): List[C] = {
      (a, b) match {
        case (Nil, _) => r
        case (_, Nil) => r
        case (Cons(ah, at), Cons(bh, bt)) => zipWith(at, bt, Cons(f(ah, bh), r))
      }
    }

    reverse(zipWith(al, bl, Nil))
  }

addPairwise を zipWith で処理すれば終了。

2016-07-24

Winows10 がクソ重い

日記

症状的には定期的にHDアクセスが 100% に突入するというもの。

そういや前も食ったなと思い出して、対処した。
マシンを再セットアップしてからやってなかったなーと

IPv6 をオフ
OneDrive 同期を停止

毎回やらないと酷いことになるって最悪のエコシステムだな。

良かれと思ってというのはあるだろうが押し付けイクナイ

だからゲーム以外でWindows使いたくないんだよ…。

2016-07-19

Scala 関数型デザイン&プログラミング:Exercize3.14-15

Scala 日記勉強

相変わらず教科書はこれ。

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)

作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
出版社/メーカー: インプレス
発売日: 2015/03/20
メディア: 単行本（ソフトカバー）
この商品を含むブログ (7件) を見る

進みは遅いが書かないと覚えなさそうだったので書く。

Exercise3.14

foldLeft or foldRight を使って、append 作れ

  def append[A](as: List[A], a: A): List[A] =
    foldRight(as, apply(a))((a, b) => Cons(a, b))

// printRec(List.append(List(1,2,3,4), 5))

って書いたら、模範解答はリストの結合だったという…
append つったら要素追加でしょうよ（；；

fpinscala/List.scala at master · fpinscala/fpinscala · GitHub

作り直し

  def append[A](as: List[A], a: List[A]): List[A] =
    foldRight(as, a)((a, b) => Cons(a, b))

// List.append(List(1,2,3,4), List(5, 6, 7))

Exercise 3.15

複数のリストを結合する関数を作れ

  def flatten[A](as: List[A]*): List[A] = {
    def flatten(head: List[A], tail: Seq[List[A]]): List[A] = {
      tail match {
        case t if t.isEmpty => head
        case t              => flatten(foldRight(head, t.head)((a, b) => Cons(a, b)), t.tail)
      }
    }
    as match {
      case a if a.isEmpty => Nil
      case a if a.size == 1 => a.head
      case a => flatten(a.head, a.tail)
    }
  }

// こうですか？わかりません
// printRec(List.flatten(
//    List(1,2,3), List(4,5,6), List(7,8,9)
// ))

仕様は多分満たしてるんだけど、実行効率がなぁ？
なんか違う気がしてきた。

fpinscala/List.scala at master · fpinscala/fpinscala · GitHub

やっぱりー（；；
なんかシグネチャ固定化して欲しいです。割と真面目に。

気を取り直してシグネチャから実装…ってこうとしか思い浮かばんから！

def concat[A](as: List[List[A]]): List[A] = foldRight(as, Nil: List[A])(append)

2016-07-12

Scala 関数型デザイン&プログラミング:Exercize3.2 - 3.13

Scala 日記勉強

前回からの続き
教本はこれ

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)

作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
出版社/メーカー: インプレス
発売日: 2015/03/20
メディア: 単行本（ソフトカバー）
この商品を含むブログ (7件) を見る

Exercise 3.2

問題

Listの最初の要素を削除する関数 tail を実装せよ。この関数の実行時間が一定であることに注意。List が Nil である場合、実装上の選択肢として他に何があるか。この質問については次章で再び取り上げる。

とのこと。

で、オブ脳な個人的に「あれ？tailってあるよね？trait でIF作ってって事？」と本家 scala.collections の List っぽく

sealed trait List[+A] {
  def head: A
  def tail: List[A]
}

case object Nil extends List[scala.Nothing] {
  override def head = sys.error("Empty head")
  override def tail = sys.error("Empty list")
}

case class Cons[+A](head: A, tail: List[A]) extends List[A]

で、なんか違うな…筆者は何を想定してるんだろう？と思って回答を見た。

fpinscala/List.scala at master · fpinscala/fpinscala · GitHub

違った…コンパニオンオブジェクトの話だったという…。
忘れたふりしてさらっと

  def tail[A](l: List[A]): List[A] = l match {
    case Nil           => Nil
    case Cons(_, tail) => tail
  }

object Exercise3_2 extends App {

  val result = List.tail(List(1, 2, 3, 4))

  def printRec(l: List[Int]): Unit = l match {
    case Nil => println("")
    case Cons(n, t) => {print(s"$n "); printRec(t)}
  }

  printRec(result)
}

Exercise 3.3

問題

Exercise 3.2 と同じ考え方に基づいて、List の最初の要素を別の値と置き換えるsetHead 関数を実装せよ。

  def head[A](l: List[A]): A = l match {
    case Nil        => sys.error("no head in empty")
    case Cons(a, _) => a
  }

/*
// 検証
object Exercise3_3 extends App {
  println(List.head(List(1,2,3,4,5)))
}
 */

どう考えたって例外しか思い浮かばない…

Exercise 3.4

先頭から N 個を削除する関数 drop を作れ

  def drop[A](l: List[A], n: Int): List[A] = {
    n match {
      case n if n <= 0 => l
      case _ => drop(tail(l), n - 1)
    }
  }

/*
object Exercise3_4 extends App {
  printRec(List.drop(List(1,2,3,4,5), 2))
}
*/

Exercise3.5

述語とマッチする場合に限り、Listからその要素までの要素を削除する dropWhile を実装せよ。

  def dropWhile[A](l: List[A], f: A => Boolean): List[A] = {
    l match {
      case Cons(h, t)  if f(h) =>  dropWhile(t, f)
      case _ => l
    }
  }

/*
object Exercise3_5 extends App {
  printRec(List.dropWhile[Int](List(1,2,3,4,5,6,7), _ < 5))
}
*/

Exercise 3.6

List の末尾を除く、すべての要素で構成された List を返す init 関数を実装せよ。

これは先頭から舐めるしかやり様がないので、要素 O(n) なんだろねー

  def reverse[A](l: List[A]): List[A] = {
    def inner(a: List[A], l: List[A]): List[A] = {
      l match {
        case Nil        => a
        case Cons(h, t) => inner(Cons(h, a), t)
      }
    }
    inner(Nil, l)
  }

  def init[A](list: List[A]): List[A] = {
    def inner(a: List[A], l: List[A]): List[A] = {
      l match {
        case Nil          => Nil
        case Cons(_, Nil) => a
        case Cons(h, t)   => inner(Cons(h, a), t)
      }
    }
    reverse(inner(Nil, list))
  }

/*
object Exercise3_6 extends App {
  val result: List[Int] = List.init(List(1,2,3,4,5))
  printRec(result)
}
*/

末尾再帰に拘らなければもっと短くなった気がする…今更か。

Exercise 3.7

考察問題なので端折る。

Exercise 3.8

foldRight 実装が前提になるので、まずは実装。
教科書通りの実装なのだが…

  def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = {
    as match {
      case Nil => z
      case Cons(x, xs) => f(x, foldRight(xs, z)(f))
    }
  }

…末尾再帰じゃない

  def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = {
    as match {
      case Nil         => z
      case Cons(x, xs) => foldRight(xs, f(x, z))(f)
    }
  }

これじゃあかんのかと思ったのだが…まぁ式に直すと f(5, f(4, f(3, f(2, f(1, z))) こんな感じになるから直感的ではないのかも？

object Exercise3_8 extends App {
  println(List(1,2,3,4,5))
  println(List.foldRight(List(1,2,3,4,5), Nil: List[Int])(Cons(_, _)))
}

結果はそう変わらず。
そりゃ head から順にとってけばそうなるよね

Exercise 3.9

リストの長さを計算する length を実装せよ。

  def length[A](as: List[A]): Long =
    foldRight(as, 0L)((_, b) => b + 1)
/*
object Exercise3_9 extends App {
  println(List.length(List(1,2,3,4,5)))
}
*/

Exercise 3.10

foldLeft を末尾再帰で実装せよ

…これってさっき書いた末尾再帰じゃね？ (･･;)

  def foldLeft[A, B](as: List[A], z: B)(f: (B, A) => B): B = {
    as match {
      case Nil => z
      case Cons(x, Nil) => f(z, x)
      case Cons(x, xs)  => foldLeft(xs, f(z, x))(f)
    }
  }

Exercise 3.11

sum, product を foldLeft で実装せよ

  def sum(ints: List[Int]): Int = foldLeft(ints, 0)(_ + _)

  def product(sd: List[Double]): Double = foldLeft(sd, 1.0)(_ * _)

Exercise 3.12

リストを逆順する reverse 関数を作れ

あれ？上で書いた reverse 関数だよね？

Exercise 3.13

foldRight をベースに、foldLeft を記述することは可能か？その逆はどうか？

foldRight の初期値に関数突っ込めばいけるか？（つまり関数スタックを高階関数でやる）

  def foldLeftViaRight[A, B](as: List[A], z: B)(f: (B, A) => B): B =
    foldRight(as, (b:B) => b)((a, g) => b => g( f(b, a) ))(z)

  def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B =
    foldLeft(reverse(as), z)((a, b) => f(b, a))

foldRight の方は割とすんなり。

2016-07-11

Scala 関数型デザイン&プログラミング:Exercize3.1

続き

サンプルコード

package fpinscala.datastructures

sealed trait List[+A]

case object Nil extends List[scala.Nothing]

case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {

  def sum(ints: List[Int]): Int = ints match {
    case Nil         => 0
    case Cons(x, xs) => x + sum(xs)
  }

  def product(sd: List[Double]): Double = sd match {
    case Nil          => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x, xs)  => x * product(xs)
  }

  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil else Cons(as.head, apply(as.tail:_*))
}

があるときに、下記の結果はなんだ！？

  val x = List(1,2,3,4,5) match {
    case Cons(x, Cons(2, Cons(3, Cons(4, _)))) => x
    case Nil => 42
    case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
    case Cons(h, t) => h + List.sum(t)
    case _ => 101
  }

見たまんま

2016-07-02

Scala 関数型デザイン&プログラミング:Exercize2.2 - 2.5

Scala 日記勉強

引き続き勉強がてら Exercise をやってみる。

Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド

作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
出版社/メーカー: インプレス
発売日: 2015/04/30
メディア: Kindle版
この商品を含むブログ (2件) を見る

Exercise 2.2

お題：配列が任意の比較関数でソートされているか判定せよ
ただし、メソッドシグネチャは def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean 固定。

…generic な高階関数なだけか…

object Exercise2_2 extends App {
  def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
    if (as.size < 2) {
      true
    } else {
      ordered(as.head, as.tail.head) &&
        isSorted(as.tail, ordered)
    }
  }

  def isOrdered(a: Int, b: Int) = a < b

  println(s"test 1 to 10 ordered ${isSorted((1 to 10).toArray, isOrdered)}")
  println(s"test 10 to 1 ordered ${isSorted((1 to 10).reverse.toArray, isOrdered)}")
}

まぁこれ位なら…

Exercise 2.3

お題：この関数を実装しろ

def curry[A, B, C](f: (A, B) => C): A => (B => C)

なんだ、ただのカレーか

object Exercise2_3 extends App {
  def curry[A, B, C](f: (A, B) => C): A => (B => C) = {
    def curried(a1: A) = (a2: B) => f(a1, a2)
    curried
  }

  def createFilledArray(i: Int, b: Boolean): Array[Boolean] = Array.fill(i)(b)

  val curried = curry(createFilledArray)
  val arr: Array[Boolean] = curried(10)(true)

  println(arr.toSeq)
}

Exercise 2.4

お題: curry の逆向きを行う、uncurryを作成せよ

object Exercise2_4 extends App {
  def uncurry[A, B, C](f: A => (B => C)): (A, B) => C = {
    def unc(a1: A, a2: B) = f(a1)(a2)
    unc
  }

  def createFilledArray(i: Int)(b: Boolean): Array[Boolean] = Array.fill(i)(b)

  val curried = uncurry(createFilledArray)
  val arr: Array[Boolean] = curried(10, true)

  println(arr.toSeq)
}

Exercise 2.5

お題：二つの関数を合成する高階関数を作成せよ。

object Exercise2_5 extends App {
  def compose[A, B, C](f1: B => C, f2: A => B): A => C = {
    def com(v: A) = f1(f2(v))
    com
  }

  def toStr(d: Double) = d.toString
  def toDouble(i: Int) = i.toDouble

  println(compose(toStr, toDouble)(65535).getClass)
}

末尾再起に比べたら緩い…。

2016-07-02

Scala 関数型デザイン&プログラミング:Exercize2.1

Scala 日記勉強

真面目にやろうかと思った。

書籍はこれ

Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド

作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
出版社/メーカー: インプレス
発売日: 2015/04/30
メディア: Kindle版
この商品を含むブログ (2件) を見る

まずは指定 N 番目のフィボナッチ数計算関数を tail call recursive （末尾再帰）な関数で実装しろとのこと。
まず単純にフィボナッチ数列の実装をしてみる。

Wikipedia 先生にお越しいただこう。

フィボナッチ数 - Wikipedia

object Exercise2_1 extends App {

  def fib(n: Long): Long = n match {
    case 0 => 0
    case 1 => 1
    case _ => fib(n - 2) + fib(n - 1)
  }

  for (i <- (0 to 10)) {
    println(s"$i : ${fib(i)}")
  }
}

これが末尾再帰かを判定するには、Scala の「scala.annotation.tailrec」を使えばいい。

  import scala.annotation.tailrec

  @tailrec
  def fib(n: Long): Long = n match {
    case 0 => 0
    case 1 => 1
    case _ => fib(n - 2) + fib(n - 1)
  }

  for (i <- (0 to 10)) {
    println(s"$i : ${fib(i)}")
  }

コンパイルすると、下記のエラーだ

[info] Compiling 1 Scala source to /Users/xxxx/Documents/projects/scala-function/part1/target/scala-2.11/classes...
[error] /Users/xxxx/Documents/projects/scala-function/part1/src/main/scala/Excercise2_1.scala:24: could not optimize @tailrec annotated method fib: it contains a recursive call not in tail position
[error]     case _ => fib(n - 2) + fib(n - 1)

it contains a recursive call not in tail position 最後の処理（return 前の最後の処理）で再起してないと言われた。

こう読み替えるとわかりやすいが、再起した結果に何らかの処理を加えてはならないということだ。

で、１時間位悩んだわけなのだが、結論から行こう。

考え方を改めないといけないのだ。n は「n 番目の計算結果を得る」という考え方をするのではなくて、「後 n 回計算する」と考える。
その上で、引数を考えると、下記で計算できるのではないだろうか？

後 5 回計算すると考えた時、

残 5 回、初期値 0
残 4 回、初期値 1 こう考えれば初期2回は特別なんだと考えて良さそうだ。
残 3 回、2 回目の値 + 1回目の値
残 2 回、3 回目の値 + 2回目の値 = (2 回目の値 + 1回目の値) + 2回目の値
残 1 回、4 回目の値 + 3回目の値 = ((2 回目の値 + 1回目の値) + 2回目の値) + (2 回目の値 + 1回目の値)

これを一般化して考えると、

残り 1 回 = 前回 + 前々回
残り 2 以上 = カウント減算、前回 + 前々回、前回

これを愚直に再起に書くとこうなる。普通に tailrec でコンパイル可能だ。

    @tailrec
    def fib(n: Long, n1: Long, n2: Long): Long = {
      n match {
        case 1 => n1 + n2
        case _ => sub(n - 1, n1 + n2, n1)
      }
    }

しかし、計算回数 0 回目、1回目という特殊ケースもあるので、事前にその答えを設定する。

  def fib(n: Long): Long = {

    @tailrec
    def sub(n: Long, n1: Long, n2: Long): Long = {
      n match {
        case 1 => n1 + n2
        case _ => sub(n - 1, n1 + n2, n1)
      }
    }

    n match {
      case 0 => 0
      case 1 => 1
      case _ => sub(n - 1, 1, 0)
    }
  }

こうなるはず。

試してみようか

  for (i <- (1 to 20)) {
    println(s"$i : ${fib(i)}")
  }

実行

$ sbt run
[info] Loading global plugins from /Users/xxxx/.sbt/0.13/plugins
[info] Set current project to sample (in build file:/Users/azalea/Documents/projects/scala-function/part1/)
[info] Compiling 1 Scala source to /Users/xxxx/Documents/projects/scala-function/part1/target/scala-2.11/classes...
[info] Running Excercise2_1 
1 : 1
2 : 1
3 : 2
4 : 3
5 : 5
6 : 8
7 : 13
8 : 21
9 : 34
10 : 55
11 : 89
12 : 144
13 : 233
14 : 377
15 : 610
16 : 987
17 : 1597
18 : 2584
19 : 4181
20 : 6765

正しそうだ

技術をかじる猫

適当に気になった技術や言語、思ったこと考えた事など。

Scala 関数型デザイン&プログラミング:Exercize3.16-3.23

Exercise 3.16

Exercise 3.17

Exercise 3.18

Exercise 3.19

Exercise3.20

Exercise3.21

Exercise3.22

Exercise3.23

Winows10 がクソ重い

Scala 関数型デザイン&プログラミング:Exercize3.14-15

Exercise3.14

Exercise 3.15

Scala 関数型デザイン&プログラミング:Exercize3.2 - 3.13

Exercise 3.2

Exercise 3.3

Exercise 3.4

Exercise3.5

Exercise 3.6

Exercise 3.7

Exercise 3.8

Exercise 3.9

Exercise 3.10

Exercise 3.11

Exercise 3.12

Exercise 3.13

Scala 関数型デザイン&プログラミング:Exercize3.1

Scala 関数型デザイン&プログラミング:Exercize2.2 - 2.5

Exercise 2.2

Exercise 2.3

Exercise 2.4

Exercise 2.5

Scala 関数型デザイン&プログラミング:Exercize2.1