コグノスケ

未来から過去へ表示

過去から未来へ表示(*)

もっと前

2014年1月24日 >>> 2014年2月6日

もっと後

2014年1月24日

permalink

編集する

Scalaでバイナリ解析2

前回の続き（2014年1月6日の日記参照）です。

おさらいすると、Booleanのリストをビット列に見立てて、任意のビット数を上位ビット〜下位ビットにOR演算し、Intのリストとして返すという処理をします。

ビット列 (0, 1, 0, 0, 1, 1, 0, 0, 0) に対して、(1ビット取る, 3ビット取る, 5ビット取る) という処理を行って、結果として (0, 4, 24) が返るイメージです。

やりたいこと


（入力1）
List(
  true, false, false, true, true, false, true, false,
  true, true, true, false, true, false, true, true
)

（入力2）
List(1, 2, 3, 4, 5, 6)

（出力）
List(1, 0, 6, 11, 21)

ビット列に相当するリストが入力1、何ビットずつまとめるか、という別のリストが入力2になります。

前回は特に触れませんでしたが、入力1と入力2の合計が異なるときの扱いについては悩みどころです。余ったリストを返すのが一番親切かもしれませんが、出力が3つになってしまいます…。

今回は、一番楽に（入力1＞入力2）なら例外スロー、（入力1＜入力2）なら切り捨て、としています。

前回の反省

前回使ったmapでは（入力:出力）の要素数を（1:1）にする必要があります。そのため(n:1）にしたければ、入力はあるが、出力はない「穴が空いた」状態を表現する必要が生じます。

Option型を使って、値はSome(値), 穴はNoneとし、最後にflattenを呼んでNoneを全部捨てましたが、あまり効率的とは思えません。

foldLeftはどうか？

入出力の要素数が一致していなくても構わないのがfoldLeftです。

foldLeftの場合


object BooleanToInt {
  def apply(g: List[Int]): ((List[Int], Boolean) => List[Int]) = {
    val o = new BooleanToInt(g)
    o.folder
  }
}

class BooleanToInt(g: List[Int]) {
  private var v = 0
  private var p = 0
  private var mp = g(0)
  private var gg = g.drop(1)

  def folder(a: List[Int], b: Boolean): List[Int] = {
    v <<= 1
    if (b) v |= 1
    p += 1

    if (p >= mp) {
      val result = a :+ v
      v = 0
      p = 0
      mp = gg(0)
      gg = gg.drop(1)
      result
    } else {
      a
    }
  }
}


val a = List(
  true, false, true, false,
  true, true, false, false,
  true, false, false, true,
  false, true, true, false
)

val b = List(1, 2, 3, 4, 5, 6)

val c = a.foldLeft(List[Int]())(BooleanToInt(b))

println(c)

コードがScala素人くさいのはさておき、SomeとかNoneが出てこない分、mapより良さそうです。

foldLeftの別形式


val c = (List[Int]() /: a)(BooleanToInt(b))

初期値のリストが長いときはfoldLeftを /: で書く手もあります。個人的には右側が被演算子になると読みづらいし、使うことはないですね…。

編集者:すずき(2014/01/25 12:57)

コメント一覧

コメントはありません。

この記事にコメントする

2014年1月25日

permalink

編集する

演算子はメソッドだ

Scalaの特徴の1つは引数が1つのメソッドを演算子のように呼び出せることです（Rubyも同じですね）。背景には、基本型を廃して「全てオブジェクト」とする、言語の文法から演算子を廃する、という設計哲学があるようです。

しかし演算子の優先順位まで消滅して1 + 2 * 3 = 9になってしまうと（全て左結合させると ((1 + 2) * 3) になる）非常に混乱しますので、コンパイラが特殊なメソッド名だけ結合の優先度を変更します。

特殊なメソッド名を付けると優先度が変わる


class MyInt(v: Int) {
  val i = v

  def +(a: MyInt): MyInt = {
    new MyInt(i + a.i)
  }

  def *(a: MyInt): MyInt = {
    new MyInt(i * a.i)
  }

  def plus(a: MyInt): MyInt = {
    new MyInt(i + a.i)
  }

  def mult(a: MyInt): MyInt = {
    new MyInt(i * a.i)
  }
}

val a = new MyInt(1)
val b = new MyInt(2)
val c = new MyInt(3)

val r1 = a + b * c
val r2 = a plus b mult c

println("r1:" + r1.i)
println("r2:" + r2.i)

r1:7
r2:9

演算子もメソッドの一種ではありますが、上記のように旧来の演算子と同名のメソッドはやはり、優先度において特別です。単純に別名のメソッドで置き換えると、結合順序が狂います。

こうまでして文法上から演算子を廃したのはなぜだろう？誰かにメリットがあるはずなのだけど、何が嬉しいのかわからん…。

Scalaのシフト演算と比較

優先度と言えばScalaは優先度付けのルールがJavaと違います。例えば、Javaはシフト演算が比較より優先ですが、Scalaは優先度が同じです。

シフトと比較が同一優先度

（JavaならOK、ScalaではNG）

scala> 1 < 1 << 2
<console>:8: error: value << is not a member of Boolean
              1 < 1 << 2
                    ^

（本来やりたいこと）

scala> 1 < (1 << 2)
res1: Boolean = true

上記の例のように、Scalaで「(1) < (1 << 2)」のつもりで「1 < 1 << 2」と書くと、左から結合されて「(1 < 1) << 2」になって型エラー（※）が起き、ちょっと不思議な気持ちになります。

あえてJavaと違う優先度にしたのはなぜだ…。

（※）1 < 1はBooleanを返し、Booleanクラスは左シフトメソッド << を定義していないため、エラーになる。

編集者:すずき(2014/01/25 15:08)

コメント一覧

コメントはありません。

この記事にコメントする

2014年1月26日

permalink

編集する

Scalaの中間記法の優先度

ScalaとJavaでシフト演算子の優先度が違うのは、決して嫌がらせではなくて「Scalaの優先度は、メソッド名の先頭の1文字で決まる」ルールから来ているようです。

素人目線だと2文字見れば良かったんじゃ…？と思いますが、そうすると何か大変なことがあったのでしょう。たぶん。

それはさておき、Scalaで中間記法を使ったときの優先度は、低い順から、


(all letters) 注: アルファベットとか
|
^
&
< >
= !
:
+ -
* / %
(all other special characters) 注: ~ とか ? とか

注: Scala言語仕様Version 2.8の6.12.3 Infix Operationsより

となっています。シフト（<<）やビット演算（& |）は、比較演算（== !=）よりも「優先度が低い」はずです。

普通の & と =

scala> 1 & 2 == 5
<console>:8: error: overloaded method value & with alternatives:
  (x: Long)Long <and>
  (x: Int)Int <and>
  (x: Char)Int <and>
  (x: Short)Int <and>
  (x: Byte)Int
 cannot be applied to (Boolean)
              1 & 2 == 5
                ^


（& が優先なら）

scala> (1 & 2) == 5
res40: Boolean = false

（== が優先なら、こっちが期待値）

scala> 1 & (2 == 5)
<console>:8: error: overloaded method value & with alternatives:
  (x: Long)Long <and>
  (x: Int)Int <and>
  (x: Char)Int <and>
  (x: Short)Int <and>
  (x: Byte)Int
 cannot be applied to (Boolean)
              1 & (2 == 5)
                ^

ビット演算の方が優先度が低いので、上記の例のように「1 & (2 == false)」と解釈されて、型エラーになります。

謎の < と =

scala> 1 < 2 == false
res41: Boolean = false


（< が優先なら）

scala> (1 < 2) == false
res42: Boolean = false

（== が優先なら、こっちが期待値）

scala> 1 < (2 == false)
<console>:8: error: overloaded method value < with alternatives:
  (x: Double)Boolean <and>
  (x: Float)Boolean <and>
  (x: Long)Boolean <and>
  (x: Int)Boolean <and>
  (x: Char)Boolean <and>
  (x: Short)Boolean <and>
  (x: Byte)Boolean
 cannot be applied to (Boolean)
              1 < (2 == false)
                ^

比較演算の方が優先度が低いので、「1 < (2 == false)」と解釈され、型エラーになるかと思ったら、なりません。意味がわかりません。

編集者:すずき(2014/01/26 03:48)