Scalaで入門 関数プログラミングその２
最長重複文字列問題
WEB+DB PRESS vol.67 の[入門]関数プログラミングをScalaでごにょごにょしてみる。
読んで字のごとく、最も重複している部分文字列を探す問題です。
*Main> maxDupStr "mississippi" "issi" *Main> maxDupStr "Ask not what your country can do for you, but what you can do for your country." " can do for you"
どんどんHaskellより見た目が複雑になっていく…。calcLen = map lenStr ってやりたい。でも同じような関数があらかた揃っているから真似はしやすかったな。
ScalaDocでListとStringBuilderを眺めていれば欲しいものは大体見つかった。
object MaxDupStr {
def main( args:Array[String] ){
println( maxDupStr( args(0) ) )
}
//-- 最長重複文字列を計算する
def maxDupStr( x:String ):String = {
val sl = x.tails.toList.sortWith( _ < _ )
extract(chooseMax (calcLen (makePair( sl ))))
}
//-- 隣り合う要素を組にする
def makePair( xs:List[String] ) = xs zip xs.tail
//-- 文字列の共通部分の長さを求める
def calcLen( xs:List[(String, String)] ):List[(Int, String)] = xs map lenStr
def lenStr( x:(String, String) ) = ( comlen(x), x._1 )
def comlen( x:(String, String) ):Int = {
def pairEq( x:(Char, Char) ) = x._1 == x._2
(x._1 zip x._2) takeWhile pairEq length
}
//-- 共通部分が一番長い要素を取り出す
def chooseMax( xs:List[(Int, String)] ):(Int, String) = {
xs maxBy( _._1 )
}
//-- 共通部分のみを残す
def extract( x:(Int, String) ):String = x._2 take x._1
}
おまけ・tailsの再発明
tailsって絶対あるだろ…と思いつつも実装してみたらやっぱり見つかったのでお蔵入りになったtails。
//def tails( x:String ): List[String] = {
// def tailsIter( str:String, xs:List[String] ):List[String] = {
// if ( str == "" ) {
// return xs.reverse
// } else {
// tailsIter( str.tail, str :: xs )
// }
// }
// val l = List[String]()
// return tailsIter( x, l )
//}
Scalaで入門 関数プログラミングその１
WEB+DB PRESS vol.67 の[入門]関数プログラミングをScalaでごにょごにょしてみる。
zip
Prelude> zip [0..] [10,20,30,40,50] [(0,10),(1,20),(2,30),(3,40),(4,50)]
zipの第一引数であるリストには「おわり」が指定されていません。この場合、必要なだけ生成することを意味します。
Scalaでは、Streamを使うとできるみたい。
scala> List( 10,20,30,40,50 ) zip Stream.from(0) res10: List[(Int, Int)] = List((10,0), (20,1), (30,2), (40,3), (50,4))
reduce - 畳み込み
Prelude> let mul(i,x) = x * i Prelude> let calc xs = foldl (+) 0 (map mul (zip [0..] xs)) Prelude> calc [10,20,30] 80
Scalaでは、
scala> def calc( xs: List[Int] ): Int = ( 0 /: (( xs zip Stream.from(0)) map (x => x._1 * x._2)))(_ + _) calc: (xs: List[Int])Int scala> calc( List(10,20,30) ) res13: Int = 80
と書けるっぽい。長い。
札幌Scala勉強会#12
コップ本第8章の「関数とクロージャー」をやりました。以下メモ。
一人前の存在としての関数
first-class function. wikipediaでは第一級関数。
値としての関数
function values.
関数リテラルを実行時にインスタンス化したもの。
FunctionNトレイトを拡張する何らかのクラスのインスタンス。
コップ本にはN(0-22)と書いてあるが、Scaladocを見ても、Function1, Function2しか見当たらない。
部分適用された関数
def sum(a:Int, b:Int, c:Int) = a + b + c val a = sum _
sum _ という部分適用関数式から、渡されていない３個の整数パラメータを受け取る関数インスタンスを作成する。
a(1,2,3) #=> 6
これは、a.apply(1,2,3) の短縮形である
someNumbers.foreach( println _ )
は、
someNumbers.foreach( println )
と書ける。
foreachの引数は関数呼び出しが必要とされる場所だから。
val a = sum _
は
val a = sum
と書けない。これは、右辺が関数呼び出しを保証していないから。
val a:Int => Int = sum
とは書ける。意味違うけど。
クロージャー
自由変数の束縛を「取り込んで」、関数リテラルを「閉じる」
(x:Int) => x + more
moreは自由変数(free variables)。ｘは束縛変数（bound variables)。
この関数リテラルから実行時に作られるインスタンスをクロージャーと呼ぶ。
閉じた項 ： 自由変数のない関数リテラル ← 厳密な意味ではクロージャーではない
開いた項 ： 自由変数を含んだ関数リテラル ← 実行時に作られた関数オブジェクト（インスタンス）がクロージャー
プログラムの実行とともに実体が変わっていく変数にアクセスする場合
クロージャーが作成されたときにアクティブだったインスタンスを使う。
scala> def makeInc(more:Int) = (x:Int) => x + more makeInc: (more: Int)Int => Int scala> var i = 1 i: Int = 1 scala> val inc1 = makeInc(i) #=> moreに１が入る。moreの束縛として、１をつかんでクロージャーが作成される inc1: Int => Int = <function1> scala> i = 99 i: Int = 99 scala> val inc2 = makeInc(i) #=> moreに99が入る。 inc2: Int => Int = <function1> scala> inc1(100) res0: Int = 101 scala> inc2(100) res1: Int = 199
連続パラメーター
echo(arr: _*)って分かりづらいね。
末尾再帰
- 単純再帰しか最適化できない
- メモ化しているわけではない
- 同じ関数を呼び出す直接的な再帰のみ
L2TP / IPSec PSK VPN を使ってアプリケーション内で接続、通信 → root化しないと無理 orz
[Android]VPNに接続し、VPN接続状態を検知する方法(PPTPのみ確認） - chakimarの日記
PPTPでの成功例があったので、L2TPも楽勝かと思いきや以下のエラーが。
01-04 16:49:40.730: ERROR/racoon(1685): couldn't find the pskey for ***.***.***.***. 01-04 16:49:40.730: ERROR/racoon(1685): failed to process packet. 01-04 16:49:40.730: ERROR/racoon(1685): phase1 negotiation failed. 01-04 16:49:40.730: INFO/racoon(1685): KA remove: 10.21.186.215[4500]->***.***.***.***[4500] 01-04 16:50:09.249: ERROR/racoon(1685): phase2 negotiation failed due to time up waiting for phase1. ESP ***.***.***.***[0]->10.21.186.215[0]
PSKの渡し方が間違っているのかなと思ってソースを見るも、特に変わったところはない。同じことをやっているアプリをいろいろと探していたら答えがあった。
http://code.google.com/p/xinkvpn/wiki/VpnKeystoreIssue
要するに、/system/bin/keystoreのkeyをエンコーディングする仮定で、uidを参照する場所があってユーザ権限だと上手くいかないよ、と。
回避するには、プログラムをroot権限で実行するか、keystoreを書き換えるか。どちらにせよroot化が必要な作業となる。
年を越す前にScala ツリーを解析してみた
Merry Christmas | Cake Solutions Team Blog
Scala初心者の自分には仕組みも去ることながら、文法や作法もとっても勉強になったのでメモ。
def main(args: Array[String]) {
\-/.
-->*<--
.
/.\
./.|.\.
/.oxo.\
./.*.|.x.\.
/.oo.|.oo.\
./.oxo.|.***.\.
/.*.oo.|.*.oo.\.
|||
}
仕組み
メソッド|||
実際に処理を行っているのはこの部分。
\.|||
中身は以下のとおり。
@tailrec
final def |||(sparkle: Boolean) {
val f = (t: Tree) =>
t match {
case _: LeftNeedle => "/"
case _: RightNeedle => "\\"
case _: Trunk => "|"
case _: Ball => "o"
case _: Spike => "x"
case _: Candle => "*"
case _: BigBall => "oxo"
case _: DoubleBall => "oo"
case _: ElectricCandle => "***"
}
def walk(t: Tree, depth: Int): List[String] = {
def walkLevel(t: Tree, acc: String,
f: (Tree) => String): (Tree, String) = {
val fx = (t: Tree) => if (sparkle) f(t).toUpperCase else f(t)
t match {
case l: LeftNeedle => (l.left, fx(l) + "." + acc)
case t: Tree => walkLevel(t.left, fx(t) + "." + acc, f)
}
}
t match {
case r: RightNeedle =>
val l = walkLevel(r, "", f)
l._2 +: walk(l._1, depth + 1)
case s: Star =>
List("-->*<-- ", "\\-/.")
}
}
val tree = "||| " +: walk(this, 0)
tree.reverse.foreach({l =>
val numSpaces = 30 - (l.length() / 2)
val padding = " " * numSpaces
print(padding)
println(l)
})
Thread.sleep(500)
|||(!sparkle)
}
val tree = "||| " +: walk(this, 0)
+:はSeqトレイトの加算メソッド。この場合は文字列"||| "にwalkメソッドの返り値Listを結合したListを返す。
walkメソッドは再帰して、行ごとの文字列をもったリストを返す。
tree.reverse.foreach～
Listの順番が根っこ（|||）からになっているので、リバースして、パディングして、出力。
val f = (t: Tree) => t match {
パターンマッチを行うメソッド。型がマッチしたら対応する文字列を返す。
def walkLevel(t: Tree, acc: String, f: (Tree) => String): (Tree, String)
一行ごとの処理メソッド。LeftNeedleが見つかるまで再帰する。|||の引数の真偽によって大文字にしたり小文字にしたりして点滅を演出。メソッドの外側のスコープで定義したfをそのまま使っているだけなので、f: (Tree) => String)はなくても良かった。
def walk(t: Tree, depth: Int): List[String]
なかでwalkLevelを回しているメソッド。walkLevelの返り値のタプルから文字列をリストに格納、クラスを次のwalkLevel関数に渡している。walkLevelが帰ってくるたびにdepth+1をしているが、実際にはdpeth:Intは使っていない。
