新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

学習記録:Scala関数型デザイン、参加記録:AtCoder Typical Contest #001

第3章:関数型プログラミングのデータ構造(続き)

リストの再帰高階関数の一般化(続き)

Exercise 3.12
  • 要素が逆に並んだリストを返す関数を記述せよ。
  def reverse[A](l: List[A]): List[A] =	
    foldLeft(l, List[A]())((x,y) => Cons(y,x))

foldLeftにリストlとNilの時に返すList[A]の空リスト、そしてCons(y,x)を返す関数を渡す。

Exercise 3.14
  • foldRightをベースとしてappendを実装せよ。
  def append[A](a1: List[A], a2: List[A]): List[A] =
    a1 match {
      case Nil => a2
      case Cons(h,t) => Cons(h, append(t, a2))
    }

  def appendViaFoldLeft[A](a1: List[A], a2: List[A]): List[A] =
    foldRight(a1, a2)((x,y) => Cons(x,y))

リストを扱うその他の関数

Exercise 3.16
  • 各要素に1を足すことで整数のリストを変換する関数を記述せよ。
  def addOne(as: List[Int]): List[Int] =
    foldRight(as, List[Int]())((x,y) => Cons(x+1, y))

foldRightで1を足していく。

Exercise 3.17
  • List[Double]の各値をStringに変換する関数を記述せよ。

Stringへの変換にはd.toStringを使う。

  def doubleListToString(as: List[Double]): List[String] =
    foldRight(as, List[String]())((x,y) => Cons(x.toString, y))
Exercise 3.18
  • リストの各要素を変更し、かつリストの構造を保つ総称関数mapを記述せよ。

第一引数のListの各要素に対し、第二引数の関数を実行してListを返す。

  def map[A,B](l: List[A])(f: A => B): List[B] =
    foldRight(l, List[B]())((x,y) => Cons(f(x), y))

これを実行すると以下のようになる。

scala> var x = List(1.0,2.0,3,4,5)
x: List[Double] = Cons(1.0,Cons(2.0,Cons(3.0,Cons(4.0,Cons(5.0,Nil)))))

scala> List.map(x)(_ + 3)
res64: List[Double] = Cons(4.0,Cons(5.0,Cons(6.0,Cons(7.0,Cons(8.0,Nil)))))

ただし、foldRightを使っているので、スタックセーフではない。
これを解消する方法の一つは、foldRightをfoldLeftにより実装し、そのfoldRightViaFoldLeftを使用することである。

  // reverseを上手いこと使う方法
  def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(reverse(l), z)((b,a) => f(a,b))

  // メソッドチェーンで上手いことやる方法
  def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

もしくは、ローカルなmutationを使う方法がある。

  def map_2[A,B](l: List[A])(f: A => B): List[B] = {
    val buf = new collection.mutable.ListBuffer[B]
    def go(l: List[A]): Unit = l match {
      case Nil => ()
      case Cons(h,t) => buf += f(h); go(t)
    }
    go(l)
    List(buf.toList: _*) // converting from the standard Scala list to the list we've defined here
  }

[参加記録] AtCoder Typical Contest #001

結果

プログラム

B問題

割りとよく出るUnionFind。正直あまり良くわかってなかった。
ざっくり言うと、

  • 各ノードは親を持つ
  • 初期値は全ノードで親=自分
  • 一番上の親=根を求める関数rootを作る
  • 根を求める際に、自分の親を根に更新することで経路を圧縮して高速化する
  • グループ化するときはどちらかの根を片方の根に統一する
  • 根が同じなら同じグループに所属しているものとみなす

という方式でグループの判別を行う方法とのこと。
グループ化の解除とかはデフォではできないので、その辺の実装が必要な場合もあるらしい。

    class UnionFind {
        // 親の番号
        int[] par;

        // 親を自分自身に初期化
        void init(int n) {
            par = new int[n];
            for (int i = 0; i < n; i++) {
                par[i] = i;
            }
        }

        // 木の根を求める
        int root(int x) {
            // 根なら自分自身を返す
            if (par[x] == x) {
                return x;
            }
            // 根で無ければ更に親を求めう
            else {
                // 経路圧縮。自分の親を根に更新する
                return par[x] = root(par[x]);
            }
        }

        // xとyが同じ集合に属する==木の根が同じか否か
        boolean same(int x, int y) {
            return root(x) == root(y);
        }

        // xとyを同じ集合にする
        void unite(int x, int y) {
            // それぞれの根を求める
            x = root(x);
            y = root(y);
            // もともと同じ集合なら何もしない
            if (x == y) return;
            
            // 根の親をどちらかの根にする
            par[x] = y;
        }
    }

勉強になりました。