Prolog学習者のための99問の練習問題をScalaで解こうという企画。難易度は(*), (**), (***)の三段階で分けられている(Prolog向け難易度の引き写し)。
解のエレガントさ、効率性にも留意せよ、ただし最初は効率より明瞭性を重視しましょうとのこと。いくつかの問題はビルトイン関数で解けちゃったりします。
以下では私が問題に取り組む際に考えていたことをだらだら述べます。こちらには私の書いた解を載せますが全てではありません。答えはリンク先で見れます。
リスト処理（問題 P1-P28）
P1 リストの最後の要素を返す
scala> last(List(1, 1, 2, 3, 5, 8)) res0: Int = 8
答えをいきなり見てScalaの基本的な書き方を再確認。去年ちょっとかじった程度だったので文法はほとんど忘れていたのだった。
型変数の付け方
def last[A](ls: List[A]): A
パターンマッチの書き方
ls match{
case x :: Nil => x
case x :: tail => last(tail)
case _ => new throw NoSuchElementException
}
を思い出す。
コーナーケースcase _（要素が1つもない場合）についても留意した。
P2 リストの最後から2番目の要素を返す
scala> penultimate(List(1, 1, 2, 3, 5, 8)) res0: Int = 5
1問目からの類推でどのようにしたらいいのかはだいたい見当がつくのだが、それに見合った記法が思い出せない。
よってこれもいきなり答えを見た。以下の書き方を覚えておく。
case x :: y :: Nil => x
P3 リストからK番目の要素を取り出す
リストの最初の要素を添字0で表すとする。
scala> nth(2, List(1, 1, 2, 3, 5, 8)) res0: Int = 2
タプルでのパターンマッチは覚えていたのですぐパスできた。
P4 リストの長さを求める
この辺りになるとだんだん頭が回ってくるようになる。今更ながら単純再帰の型がわりと決まりきっていることを感得する。
def length[A](ls: List[A]): Int = ls match{ case Nil => 0 case h :: tail => 1 + length(tail) }
P5 リストを反転させる
単純な再帰でやると計算量オーダーがになる。これはリストの末尾への結合にかかる時間がリストの要素数分であるせい。継続渡しで要素をリストの先頭に継ぎ足していく方式にすれば
でいけるでしょう。もっとも解答見るまで忘れてたけど。
P6 リストが回文になっているか判定する
P5のような問題の次に必ず出される問題ですね。
P7 入れ子になったリストを平坦化する
解答はflatMapを使っているのですが、『mapを適用したあとリストの入れ子を解消する操作』ってなんかずるいですよね。
最初に書いたコードはこんな感じ。
object Flat{ def flatten(ls: List[_]): List[_] = ls match{ case List() => List() case (xs : List[_]) :: (ys : List[_]) => flatten(xs) ::: flatten(ys) case x :: (xs : List[_]) => List(x) ::: flatten(xs) } }
パターンマッチが微妙に混乱している。Flatten a list - Rosetta Codeを見るともっとすっきり書いて良い事が分かる。
P8 連続した同じ要素を一つにまとめる
scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)
これはすぐに分からなかった。dropWhileを覚えていれば、という感じ。
P9 連続する同じ要素をリストにまとめる
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))
spanの使い方を覚える。
def pack[A](ls: List[A]): List[List[A]] = ls match{ case Nil => Nil case _ => { val (packed, next) = ls span { _ == ls.head } packed :: pack(next) } }
P10 リストのランレングス符号をとる（P9の関数を利用して）
P9の返り値の型がList[(Int, Symbol)]になっているだけ。P9にもたついたので自習するつもりで一から書いたらP13と重複していた。言われたことを素直にやらないとこうなる(´・ω・｀)
P11 リストのランレングス符号をとる（長さ1の文字は(1, 'a)でなく'aとする。
Aか(Int, A)型を返したいのだからEitherにするとスッキリする。
P12 ランレングス符号化されたリストをデコードする
簡単。解答のList.makeは新しめのScalaではdeprecateなのでList.fillにしましょう。
P13 リストのランレングス符号をとる
直接実装せよといってもP9と大した差はない。ちょっといじるだけ。
P14 それぞれの要素を複製する
scala> duplicate(List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)
ところでリンク先の解答はここでもflatMapを使ってるけどやはり教育的じゃないと思う。
def duplicate[A](ls: List[A]): List[A] = ls match{ case Nil => Nil case h :: tail => List.fill(2)(h) ::: duplicate(tail) }
P15 与えられた数字の回数だけそれぞれの要素を複製する
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)
P14をちょっと変えるだけ。
P16 N番目ごとに1つ要素を落としたリストをつくる
ちょっと日本語がわかりづらいかもしれないけど下を見れば単純。
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)
この辺りから継続渡しを始める。
def drop[A](n: Int, ls: List[A]): List[A] = { def dropR(n: Int, ls: List[A], pn: Int): List[A] = ls match{ case Nil => Nil case h :: tail if pn % n == 0 => dropR(n, tail, pn+1) case h :: tail => h :: dropR(n, tail, pn+1) } dropR(n, ls, 1) }
P17 リストを2つのリストに分割する
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))
takeとdropでやるのが普通だしそれが一番関数的なんだけど頭を使うために継続渡しする。
def split[A](n: Int, lists: List[A]): (List[A], List[A]) = { // ls: left lists, rs: right lists def splitR(n: Int, ls: List[A], rs: List[A]):(List[A], List[A]) = (n, rs) match{ case (_, Nil) => (ls.reverse, rs) case (0, rs) => (ls.reverse, rs) case (n, h :: tail) => splitR(n - 1, h::ls, tail) } splitR(n, Nil, lists) }
P18 リストのiからk番目までの要素を抜き出す
一応0を最初の要素としていることに注意。
scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) res0: List[Symbol] = List('d, 'e, 'f, 'g)
もうこれはtakeとdropで実装するのが自然だろうということで（妥協）車輪を再発明。
def slice[A](i: Int, k: Int, ls: List[A]):List[A] = { def drop(i: Int)(ls: List[A]): List[A] = (i, ls) match{ case (0, _) => ls case (n, h :: tail) => drop(n-1)(tail) } def take(k: Int)(ls: List[A]): List[A] = (k, ls) match{ case (0, _) => Nil case (n, h :: tail) => h :: take(n-1)(tail) } take (k-i) (drop(i)(ls)) }
P19 リストを回転させる。N番目以降の要素を一番左へ。
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)
はじめ負の入力に気づかずP17を流用して事足れりとしていた（なんという注意力散漫！）。
リストの長さで剰余をとったあと負の値に関する条件分岐をする。大したことはないけど今までの問題に比べると泥臭い作業。
P20 K番目の要素を削除したリストと削除した要素のタプル
scala> removeAt(1, List('a, 'b, 'c, 'd))
res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)
def removeAt[A](k: Int, ls: List[A]): (List[A], A) = { def removeAtR(k: Int, ls: List[A], rs: List[A]):(List[A], A) = (k, rs) match { case (_, Nil) => throw new NoSuchElementException case (0, h :: tail) => (ls.reverse ::: tail, h) case (k, h :: tail) => removeAtR(k-1, h :: ls, tail) } removeAtR(k, Nil, ls) }
P21 リストに対して与えられた位置に要素を挿入するメソッド
scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)
splitAtも使わずに。
def insertAt[A](elem: A, n: Int, ls: List[A]): List[A] = (n, ls) match { case (0, _) => elem :: ls case (n, h :: tail) => h :: insertAt(elem, n-1, tail) }
P22 rangeの再発明
def range(start: Int, end: Int): List[Int] = { def rangeR(num: Int, count: Int): List[Int] = count match { case 0 => List(num) case _ => num :: rangeR(num+1, count-1) } rangeR(start, end-start) }
P23 リストからランダムにN個の要素を選んだリスト
util.Randomを使ったことがなかったので答えを見た。再帰するごとに(new util.Random)していては高くつくのでここでも継続渡しする。
P24 1..Mの数字からN個の異なる数のリストを得る
P22, P23から簡単に作れる。
P25 与えられたリストからランダムな並びのリストを作る（シャッフリング）
P23から即座に、
def randomPermute1[A](ls: List[A]): List[A] =
randomSelect(ls.length, ls)
すればよいことはわかる。純粋関数的にシャッフルするためには色々あるらしい。
// Efficient purely functional algorithms for shuffling are a lot harder. One
// is described in http://okmij.org/ftp/Haskell/perfect-shuffle.txt using
// Haskell. Implementing it in Scala is left as an exercise for the reader.
P26 与えられたリストからN個の要素を選ぶ組み合わせのリスト（combination）
その要素を選ぶか/選ばないかで再帰した。要素が尽きたらNil、選ぶ個数が尽きたらそれまでに選んだリストを返す。
def combinations[A](n: Int, ls: List[A]): List[List[A]] = { def csR(n: Int, rs: List[A], ls: List[A]): List[List[A]] = { (n, ls) match{ case (0, _) => List(rs.reverse) case (_, Nil) => Nil case (n, h :: tail) => csR(n, rs, tail) ::: csR(n-1, h :: rs, tail) } } csR(n, Nil, ls).reverse }
P27 リストの互いに素なグループ分けを行う
基本的にP26の結果を利用する。
a)問題
9人のグループを2, 3, 4人に分ける組み合わせをすべて列挙する。
scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida")) res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), List(Flip, Gary, Hugo, Ida)), ...
b)問題
与えられた任意のグループ分けで分ける組み合わせを列挙する。
scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida")) res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), ...
自力では解けなかった。とくにb)問題はまだちょっと頭の中で消化できていない。
P28 リストをサブリストの長さに応じてソートする
a)問題
リストを要素に含むリストがあるとする。その要素リストの長さに応じて昇順にソートする。
def lsort[T](ls: List[List[T]]): List[List[T]] = {
ls.sortBy(_.length)
}
ここに来て組み込み関数を使うずるさ。
b)問題
リストの要素リストの長さの出現頻度に応じて昇順にソートする。
def lsortFreq[T](ls: List[List[T]]): List[List[T]] = { val countmap = mutable.Map[Int, Int]() val lens = ls map {_.length} lens.foreach ((i) => { val count = countmap.getOrElse(i, 0) countmap.update(i, count+1) } ) ls.sortBy(x => countmap(x.length)) }
