連長圧縮

孤独のHaskellという記事があった。

遅刻して現場に付いたらRLEしてみようという例題(“AABBCCC"を"A2B2C3"にする関数を書こう)をやっていて

画像フォーマットのgifとかこういう圧縮やってんだよね。仕組みはよく知らないけど、AABBCCC→A2B2C3くらいならやれそうじゃん？
甘かった。

連長圧縮はともかく文字列の分割を考える

文字列をx:y:xsとかで取り出してx==yのとき云々とか考えてたけどなかなかうまく行かず、あちこちをさまよっている間に、groupという関数の存在を知ります。

1
2
3

Prelude> import Data.List
Prelude Data.List> group "aabbccc"
["aa","bb","ccc"]

ほー。これは便利だ。あたしこういう関数の存在も知らないままトライしようとしてるわけか。無謀だなあ。
で、これの仕掛けはどうなってんの？
たしかHoogleというサイトが便利だったはず。

Data.List.group

groupData.Listの中に収録されてる。
実装も見られるみたいなので恐る恐る見てみる。こええ。

1
2

group                   :: Eq a => [a] -> [[a]]
group                   =  groupBy (==)

短い！！ groupByに(==)を与えた、えーと部分適用？の状態なんだな。
group “aabbccc”
と
groupBy (==) “aabbccc”
はおなじなんだということな？

1
2
3
4

*Main Data.List> group "aabbccc"
["aa","bb","ccc"]
*Main Data.List> groupBy (==) "aabbccc"
["aa","bb","ccc"]

ははーなるほど。

Data.List.groupBy

「special case of groupBy」とのことなので、次は

groupByを見てみる。

1
2
3
4

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

書いてあることはわからんながら、たった数行で表現しちゃうものなのね。根拠無く、もっと長大な何かをイメージしてた。

効果的な切り取り方をしてると感じたのは

1
2

groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

ここ。
spanの第一引数に1文字目と等しいか比較する関数(eq x)を食わせ、第二引数に1文字目いがいの文字列(ABBCCC)を食わす。
返り値はパターンマッチングでリストysとリストzsとして受け取る。スマートだなあ。

span

循環参照的泉鏡花的らせんに迷いこむような錯覚を覚え始めましたが、こんどはspanというのを見てみよう。その前に使ってみよう。

1
2

*Main Data.List> :t span
span :: (a -> Bool) -> [a] -> ([a], [a])

なんかこういう型宣言をすぐ取ってこれるのは便利なんだなと思えるようになってきた。
真偽値を返す関数とリストの何かを渡すと、タプルにふたつのリストを内包したブツを返す。
左様で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

*Main Data.List> span (==1) [1,2,3]
([1],[2,3])
*Main Data.List> span (==1) [5,1,2,3]
([],[5,1,2,3])
*Main Data.List> span (==2) [5,1,2,3]
([],[5,1,2,3])
*Main Data.List> span (==2) [1,2,3]
([],[1,2,3])
*Main Data.List> span (==2) [2,3]
([2],[3])
*Main Data.List> span (==2) [2,2,2,3]
([2,2,2],[3])

狙った値で切り取れるんだコレ。便利だなー！
“AABBCCC"の"A"で"ABBCCC"をspanするわけだな！

1
2

*Main Data.List> span (=='A') "ABBCCC"
("A","BBCCC")

はいはいはいはい。

※以下長くなったので畳みます

spanの解説はこちら。
こちらの実装もこれまた短くて、

1
2
3
4
5

span                    :: (a -> Bool) -> [a] -> ([a],[a])
span _ xs@[]            =  (xs, xs)
span p xs@(x:xs')
         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
         | otherwise    =  ([],xs)

なんなのもう。なんでこんなシンプルに書けちゃうの。すごいな。読めないけど。
spanの定義まで降りてきたところで、初見の関数はこれ以上無いっぽい。
spanの動作を見届けたら戻ろう。
1行ずつ読み下していきます。

1

span                    :: (a -> Bool) -> [a] -> ([a],[a])

関数とリストを渡して要素がふたつあるリストを返す。

1

span _ xs@[]            =  (xs, xs)

関数の中身はどうでもよくて(_)、リストが空だった場合には[[],[]]を返す。
そうなんだ？動かしてみる。

1
2

Prelude> span (==2) []
([],[])

あーなるほど。
んじゃ次の行。

1

span p xs@(x:xs')

関数名　条件p　リストxsを渡す場合
リストxsはx:xsが成立する場合

1

         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)

ここの書き方がピンと来ない。
この「p x」ってなんだ。
あたしにとってp xの位置は、

前回の記事でいうところの

1
2
3
4
5
6
7

bmiTell :: Double -> Double -> String
bmiTell weight height
        | bmi <= 18.5 = " yase"
        | bmi <= 25.0 = " hutu-"
        | bmi <= 30.0 = " debu"
        | otherwise   = " very debu"
        where bmi = weight / height ^ 2

こういうアレで、bmi <= 18.5が成立する場合に=の右側の内容を実行するというイメージなんだけど、pとxがなんだって？何だここは。
pとxがどうなのかの記述が特にないということは、べつにここp xって書いてなくてもいいの？なんか書く必然性があるから書いてるんだろうけどさっぱりわからない。
ちょっとモヤモヤしますが、さしあたり、p xのところは見ないことにして、等記号の右側を見ていくことにします。
let(ys,zs)というのは、いきなりここで変数ふたつを定義しますということだな。
（10分後くらい）
ちょっとわかってきた。
値を展開しちゃった状態で書き直す。
pは(==‘A’)とかの

条件が入り、xはリストの先頭1

文字が入るから、span (==‘A’) “AABBCCC"の場合

1
2
3

p x = ...
↓
(=='A') 'A' = ...

で、たしかに条件式になるんだわ。ghciでも

1
2

Prelude> (=='A') 'A'
True

ははーなるほど。よくこんな書き方思いつくな。
このふたつに入る値は、大元のリストxsにとってのtailであるxs’をspanした返り値、切り出した頭と尻尾を分けてys,zsに渡すということな。
（3時間後くらい）
ちーともわからんのでイライラしてたが、なんとか文法を見つけてこれた。

let式　プログラミング/Haskell/入門 - Flightless wing> letとinの間で定義した関数を，inの後ろで定義した関数内で使うことが出来ます．

入れ子になっている関数の定義は，letよりもインデントの深い所でしてください．

ということは、

1

         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)

let～inの間は関数の定義

1

(ys,zs) = span p xs'

あーそう、それなら読める。当初の文字列がAABBCCCだとすると、ここは、

1

(ys,zs) = span (=='A') "ABBCCC"

になるということだわな。
で、ここで定義した関数をinの後ろの関数で使う。

1

(x:ys,zs)

かんすう？
タプルの定義じゃないのコレ。
またghciで試す。

1
2
3
4
5

Prelude> let buff = "AABBCCC"
Prelude> let (ys,zs) = span (=='A') $ tail buff in ('A':"A","BBCCCC")
("AA","BBCCCC")
Prelude> let (ys,zs) = span (=='A') $ tail buff in ('A':"AB","BCCCC")
("AAB","BCCCC")

書き方の問題もあろうが、とにかくlet~inをまったく無視して、in以降で定義されたリストが帰っている。
おまけにlet (ys,zs)って書いてあるんだからysとzsに値を渡してるというふうに見えるものの、値は帰ってきてコンソールに表示される。
そういえば$記号は文末までのカッコである、というような話だったが、inあたりを文の終わりと認識して動いている。
ややこしいなー。

1

span p xs'

これで別れた文字列ふたつのリスト（“A"と"BBCCC”）の、一個目にxを足して、“AA"と"BBCCC"を返す動作なんだよということは大体わかった。ちょっと納得まではできてない。世界をどういうふうに眺めるとこういう思考ができるんだろうか。

長くなったけど先を進みます。

1

         | otherwise    =  ([],xs)

そうでない場合には、([],xs)を返す。
うーん。

Prelude> span (==2) [2]
([2],[])
Prelude> span (==2) [1]
([],[1])

後者のケースとか、

Prelude> span (==‘X’) “AABBCCC”
(””,“AABBCCC”)

に当たる。

文字列を分解するという仕事そのものはとても単純な話なのに、それについて追っかけまわしたら意外と旅になっちゃいました。
染み込んでいない箇所がいくつかあるにせよ、どんな動作をしているのかはぼんやり見えました。
ふう。

結果

1
2
3
4
5
6

--"AAA" -> "A3"
cntstr :: [Char] -> [Char]
cntstr xs@(x:xs') = x : show(length xs)

strgrp :: [Char] -> [Char]
strgrp xs = foldl (++) [] $ map cntstr $ group xs

うん。

1
2

*Main Data.List> strgrp "AABBCCCDDD"
"A2B2C3D3"

うんうん。できた。いきなりでてきたfoldlは、よくわかってないが畳み込みというやつだ。右と左とがあるらしいがよくわからない。
さいしょ、

1

strgrp xs = map (++) $ map cntstr $ group xs

こんな書き方を目論んだんだが、

1
2
3
4
5
6
7
8
9

Prelude Data.List> map (++) ["aa","bb","ggg"]

:1:1:
    No instance for (Show ([Char] -> [Char]))
      arising from a use of `print'
    Possible fix:
      add an instance declaration for (Show ([Char] -> [Char]))
    In a stmt of an interactive GHCi command: print it
Prelude Data.List> show $ map (++) ["aa","bb","ggg"]

おこられるんだよね。
なので「あっそういえば畳み込みというやつがあったようなー」と、ふと思って試したのが上の完成形。よかった。
はー。
頭使ったよ。

関連記事