Scala 関数型デザイン&プログラミング:Exercize3.14-15
相変わらず教科書はこれ。
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)
Scala 関数型デザイン&プログラミング:Exercize3.2 - 3.13
前回 からの続き
教本はこれ
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 の方は割とすんなり。
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 }
見たまんま
Scala 関数型デザイン&プログラミング:Exercize2.2 - 2.5
引き続き勉強がてら 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) }
末尾再起に比べたら緩い…。
Scala 関数型デザイン&プログラミング:Exercize2.1
真面目にやろうかと思った。
書籍はこれ
Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド
- 作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
- 出版社/メーカー: インプレス
- 発売日: 2015/04/30
- メディア: Kindle版
- この商品を含むブログ (2件) を見る
まずは指定 N 番目のフィボナッチ数計算関数を tail call recursive (末尾再帰)な関数で実装しろとのこと。
まず単純にフィボナッチ数列の実装をしてみる。
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 前の最後の処理)で再起してないと言われた。
こう読み替えるとわかりやすいが、再起した結果に何らかの処理を加えてはならないということだ。
で、1時間位悩んだわけなのだが、結論から行こう。
考え方を改めないといけないのだ。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
正しそうだ
投票が近づいて来たので、40代以下に言っておこうか
なんで皆の税率が上がって、将来の年金まで気にするようになるのか、その理由をざっくり説明する。
なんで老人向けの介護とか福祉がこの時期叫ばれるのか?
まず、この時期になると声高に叫ばれることがある。それは高齢者福祉だ。
最近では少子化対策で児童福祉というパターンも多い。
そんな中気にして欲しいのは、「働く世代である 20-40 に対する内容が声高に叫ばれないのは何故か?」だ。
結論から言おう。
その世代は投票しないから色々言っても無駄だとどの政党も諦めてるからだ
公益財団法人、明るい選挙推進協会 のデータを見ればわかる。
もっとも投票しているのは 60 代を筆頭に、50,70,40 代と続いている(平成26年度)。
つまり政治家は、この年代にアピールした方が当選しやすいって寸法だ。
邪推かもしれないが、少子化対策云々を声高にする背景すら、50 代が 2 位という数字を見れば、「そろそろ引退するし、今後養ってくれる世代を増やしたい」と思っている世代の投票を拾いたいという意図が見え隠れしてるとも言えないだろうか?
そうは言ってもこれまでやってこれたんじゃない?
そういう人は多そうだ。
だが、英国の離脱を機に、続々離脱しようかという声が上がり始め、EU 自体崩壊し始めてる。
要するに目に見える世界経済の混乱が迫ってるんだ。
さぁこれで働く世代だけ割を食う構造で、不幸にならないと言い切れるのか?
ここで怖い話を教えておこう。
そんな状況を生み出した英国の EU 離脱なのだが、その原因は ご老人達 だという事実を。
6/25 日の 日本経済新聞 の記事を抜粋しよう。
欧州連合(EU)離脱の是非を問いかけた23日の英国民投票では、英国人の世代間の意識の違いが浮き彫りになった。52%対48%と僅差で離脱派が勝利したが、投票先を年代別にみた各種調査では、年齢が高くなるほど離脱を支持し、逆に30代以下の若年層は残留が多かった。
ニュースサイトが消えた場合も考えて、失礼かもしれないがグラフも転載させてもらう。
そう、離脱を望んだのは紛れもなくご老人達だ。
ではご老人達はなぜ離脱に傾いたのだろうか?それは英国ご当地新聞の BBC に聞いてみる。
- 離脱すれば経済打撃があるという残留派、離脱の影響を悪しざまに言うのは、私利私欲から英国を批判する無責任な金持ちエリートだと一蹴する離脱派確執があった
- EU 離脱で浮いた金をNHS(国民医療サービス)に3億5000万ポンド突っ込むと公約があった
- 移民が増えたら混乱するけど、拒否するなら EU の協調ルールは邪魔
なんてのがある。
残留派が若い世代というのは、自由移動と経済域が広ければ、その分雇用があるからだ。
しかし既に引退したご老人に雇用なんざ知った事ではない。そんな事より老後衰えた体に福祉を欲しがったんだ。
それを引き起こしたのは投票を軽く見た若い世代の責任もある
政治に興味がないと放置した挙句、楽観視してたら後になって慌てたわけだ。
そして投票のやり直しを求めた
http://news.tbs.co.jp/newseye/tbs_newseye2806734.htmlnews.tbs.co.jp
しかしそれは叶わない。
覆水盆に返らずとはこのことだ。
ご老人の方が投票率が高い日本でも同じ事は起こり得る
どうだろう?日本は周囲に気を使うとも言われているが、 こんな記事 だってある。
「騒がしい」など従来の静かな環境を維持したい高齢者らの苦情を受けて開園を延期したり、「平穏な日常生活が侵害された」として、開園後に訴訟に発展したりするケースもある。
誰もが好々爺なんていいもんじゃない(もちろん居ないとは言わないが)。
彼らも一人の人だ。散々働いた後の老後なんだし好きにしたいという気持ちだってあるだろう。
悪いがこんな記事を書いている自分だって、投票先は自分の利害で決める。
止める手はあるのか?
はっきり言えば今すぐの改善はできない。
しかし、動かなければ永久に改善できない問題でもある。
どうするか?
わかりきった事だ。
「白紙でも良いから若い世代が投票すれば良い」
今からマニフェスト読み直して吟味して…なんてのは正直難しいだろう。
だから今すぐそんな事をするくらいなら白紙で良いんだ。
少なくとも若い世代は投票する意思があるという事を示すんだ。
若い世代が白紙(支持政党はない)と投票した事になる。
そうすればその票は要するに浮動票なんだ。
票集めが必要な政治家はその票を無駄にはしたくない。
「この世代は取り込む価値がある」
と思わせる事が出来れば良いのだ。
そうすれば、働く世代に有利な条件を提示してくるようになる。
当然ながらその後も継続しないと「なんだ一過性かよ」と見放されること請け合いなのだが…
投票所まで歩って何分だろう?移動は面倒かも知れないが、建物の中に入って白紙でも出して出てくるなんてものの十分の話だ。
「自分一人がやったって変わらないでしょう?」そういうから阿呆なのだ。
有権者は無数にいるんだが、さっきの話を思い出そう。
黙ってれば老人共の為だけに君らの生活が犠牲になっていくという事実を。
みんな言ってる事だけど、投票にも参加しない奴に、政治や税金の愚痴を言う資格なんざない。
愚痴を言う位なら数年に1回の数時間位、白紙投票でもして「俺はお前らを支持しない!」と声高に言ってみてはどうだろう?
一応
煽るような事ばかり書いてすまないとは思う。
しかし 現実問題 なんだ。
僕もそうだが、これからも日本で生きるなら避け続けるほど事態は悪化する。
そんな危機感を持ってるのは僕だけではないはずだ。
願わくば、少しでも気にしてくれる若者の目に留まる事を祈ろう。