日常系のゆるふわな何か

  • 4
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

この記事はAizu Advent Calendar 2015の11日目のために書かれた記事です。

やること

最近使ってるエディタの話
Scalaで継続を理解したい話

最近使ってるエディタの話

「それ、Sublime Textですか?」って声かけられたのでatom editorの紹介を軽くします。僕もそんなに使い込んでるわけじゃないですが.......

Atomとは

GitHubが開発したオープンソースのテキストエディタ。

スクリーンショット 2015-12-11 10.45.23.png

project-manager(左のやつ)とminimap(右のやつ)入れて
hurumeki/atom-pronama-chan
で美雲あんずちゃんを召喚して癒しを得ています。卒論に負けないように強く生きていきたい。
もっと知りたい方はATOM-editor Advent Calendar 2015とかも見ると良いでしょう。

Scalaで継続を理解したい話

最近Scalaを勉強し始めて、今は継続を理解しようとしています。

考えたこと

注意:以下の内容は僕が自分で考えたことなので間違ってる可能性がありまし、そもそも継続の題材として不適切かもしれません。

何がしたいのか

次のc++で書かれたコードと大体同じことをしたい。

#include<iostream>

using namespace std;

int main(void){

  int a[5]={1,2,3,4,5},b[6];

  for(int i=0;i<5;i++)b[i]=0;

  for(int i=0;i<5;i++)
    b[i+1] = b[i] * 10 + a[i];

  for(int i=1;i<=5;i++)
    cout << b[i] << (i<5?" ":"\n");

  return 0;
}

実行結果

1 12 123 1234 12345

まず、何も考えず再帰関数を書く。

object Main {

  val t: List[Int] = List(1,2,3,4,5)

  def h(i: Int, a: Int): Int = t(i) + a * 10

  def rec(i: Int): Int = if(i==0) h(0, 0) else h(i, rec(i-1))

  def main(args: Array[String]): Unit = {
    val res = rec(4)
    println(res)
  }
}

実行結果

12345

これを、リストを返すように書き直す。

object Main {

  val t: List[Int] = List(1,2,3,4,5)

  def h(i: Int, a: Int): Int = t(i) + a * 10

  def rec(i: Int): List[Int] =
    if(i==0)List(h(0,0))
    else {
      val tmp = rec(i-1)
      h(i, tmp(0)) :: tmp
    }

  def main(args: Array[String]): Unit = {
    val res = rec(4)
    println(res)
  }
}

実行結果

List(12345, 1234, 123, 12, 1)

逆だけど大体同じことができてるので良しとしよう。
で、このrec関数は末尾再帰ではない。これを末尾再帰にするのだが、まず最初の 12345 を返す関数を末尾再帰にしてみる。

import scala.annotation.tailrec

object Main {

  val t: List[Int] = List(1,2,3,4,5)

  def h(i: Int, a: Int): Int = t(i) + a * 10

  @tailrec
  def rec(i: Int, f: (Int, Int) => Int): Int =
    if(i==0)f(0, 0) else rec(i-1, (j,a) => f(i, h(j, a)) )

  def main(args: Array[String]): Unit = {
    val res = rec(4,h)
    println(res)
  }
}

そして、リストを返すようにする。

import scala.annotation.tailrec

object Main {

  val t: List[Int] = List(1,2,3,4,5)

  def h(i: Int, a: Int): Int = t(i) + a * 10

  @tailrec
  def rec(i: Int, f: (Int, Int) => List[Int]): List[Int] = {
    if(i==0)f(0, 0) else rec(i-1, (j,a) => h(j,a) :: f(i, h(j,a)) )
  }

  def main(args: Array[String]): Unit = {
    val res = rec(4,(a,b) => List(h(a,b)))
    println(res)
  }
}

継続ってこう言うことなんだろうか?よくわからないけど、話を先に進めよう。
トランポリン化でStackOverflowの回避
を参考に、最初の 12345 を返す関数を書き直してみる。

import scala.annotation.tailrec

object Main {

  val t: List[Int] = List(1,2,3,4,5)

  def h(i: Int, a: Int): Int = t(i) + a * 10

  sealed trait TailRec[A] {
    final def run: A = this match {
      case Return(a) => a
      case Suspend(f) => f().run
    }
  }

  case class Return[A](v: A) extends TailRec[A]
  case class Suspend[A](resume: () => TailRec[A]) extends TailRec[A]

  @tailrec
  def rec(i: Int, f: (Int, Int)=>TailRec[Int]): TailRec[Int] =
    if(i==0)f(0, 0)
    else rec(i-1, (j,a) => Suspend(() => f(i, h(j, a)) ))

  def main(args: Array[String]): Unit = {
    val res4 = rec(4, (a,b) => Return(h(a,b)))
    println(res4.run)
  }
}

まだ全然理解できてないけど、これはおそらくトランポリン化できているはずで、Listを大きくして試してみよう。

import scala.annotation.tailrec

object Main {

  //val t: List[Int] = List(1,2,3,4,5)
  val t: List[Int] = List.fill(100001)(1)

  def h(i: Int, a: Int): Int = (t(i) + a * 10)%1000000

  sealed trait TailRec[A] {
    final def run: A = this match {
      case Return(a) => a
      case Suspend(f) => f().run
    }
  }

  case class Return[A](v: A) extends TailRec[A]
  case class Suspend[A](resume: () => TailRec[A]) extends TailRec[A]

  @tailrec
  def rec(i: Int, f: (Int, Int)=>TailRec[Int]): TailRec[Int] =
    if(i==0)f(0, 0)
    else rec(i-1, (j,a) => Suspend(() => f(i, h(j, a)) ))

  def main(args: Array[String]): Unit = {
    val res4 = rec(100000, (a,b) => Return(h(a,b)))
    println(res4.run)
  }
}

できてるっぽい......?

まとめ

atomというエディタがある。
よくわからないまま話を進めようとしたらわからなくなった。