Programmer's Note

コード読み書きの備忘録。

Haskellでミニマムな正規表現のmatch関数を実装してみる

「ビューティフルコード」(オーライリー・ジャパン)のしょっぱなの章で、 カーニハン先生がロブ・パイクさんのミニマムな正規表現のmatch関数のソースコードを紹介していた。

たった30行ほどのC言語コードで、下記正規表現をサポートする。

文字 意味
c 文字cそのもの
. 任意の一文字
^ 文字列の先頭にマッチ
$ 文字列の末尾にマッチ
* 直前の文字の0回以上の反復

95%の用途はこれで足りると書いてあったが、さもありなん。 短くて日常のほとんどのケースで用が足せる簡潔なプログラムは、まさにUNIX精神そのもの。

この本のパイクさんのコードに触発されて、Haskellで同等のものを書いてみた。

ミニマム正規表現match関数Haskell

match_here :: [Char] -> [Char] -> Bool
match_here [] _ = True
match_here (x:xs) []
    | x == '$' && xs == [] = True
    | otherwise = False
match_here (x:xs) (y:ys)
    | x == y || x == '.' = if xs /= [] && head xs == '*' 
                           then match_repeat x (tail xs) ys
                           else match_here xs ys
    | otherwise = False


match_repeat :: Char -> [Char] -> [Char] -> Bool
match_repeat _ [] _ = True
match_repeat _ _ [] = False 
match_repeat c (x:xs) (y:ys)
    | x == y = match_here xs ys
    | c == y || c == '.' = match_repeat c (x:xs) ys
    | otherwise = match_here xs (y:ys)


-- match regex string 
match :: [Char] -> [Char] -> Bool
match _ [] = False
match (x:xs) (y:ys)
    | x == '^' = match_here xs (y:ys)
    | match_here (x:xs) (y:ys) = True
    | otherwise = match (x:xs) ys

使用例

*Main> match "^a.*1" "abccfb1"
True
*Main> match "abc" "abccfb1"
True
*Main> match "c.*1$" "abccfb1"
True
*Main> match "ccd" "abccfb1"
False

ロブ・パイクさんのコードは、再帰とポインタを巧みに使っていて、 ほとんどC言語関数型プログラミングをしているようなもの。

このプログラム構成のアイディアはそのまま使った感じだが、 コードを見ながら移植だとつまらないので、 一度みた構成を思い出しながら、Haskellで実装するというスタイルをとった。

Haskell初心者なので、実はもっと簡潔に書けるかもしれない。 が、実際書いてみるとHaskell言語はかなり見通しがよいと思った。 パターンマッチング、条件分岐や関数宣言の簡潔な記法、が効いているな。

続:Haskell/Clojureでrepeated_combinationを実装してみる

http://hifistar.hatenablog.com/entry/2018/03/24/131654:repeat_combinationを実装してみるの続き。

この前書いたコードは結構無駄が多くて、実はもっとぜんぜん簡潔にコードが書けた。 ここまで簡潔なコードにブラッシュアップできたのは、Haskellのおかげだなと。

Clojureだけの場合は、ある程度で満足して、先に思考を進めることはあまりしなかった。 Haskellでコードを書くと、違う視点でものごとを考えることができる、というのが大きい。

Haskellは、文字通り「型にはまる」とコードがものすごくシンプルになる、と実感する。 関数のInput/Outputの型(データの抽象度のレベル感)を揃えることが、が非常に大事だと学んだ。

これはプログラミングの基本中の基本かもしれないが、なかなか意識しても難しい。 Haskellの場合は強制的にそれをさせる、という意味でかなり良い。

Clojureの場合は、そろってなくてもプログラムが組める。自由度が高い。 ifなどの条件文で動的に型をチェックして、処理を振り分けてしまえる。 これはもろ刃の剣で、素早くコードを組んだり変更したりするには向いているが、かなり意識しないとプログラムの構造がmessyになる。

双方をやることでいろいろ気づきが出てきて、「結局こういうことじゃね?」という風に理解が深まる。 短いコードで表現できるアルゴリズム系の勉強に、結構いいんじゃなかろうかと思った。

さて、あらためてrepeat_combinationの実行例:

*Main> repeat_combination [1,2,3] 2
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
*Main> repeat_combination [1,2,3] 3
[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]
幅優先で組み合わせする場合

結局こういうことだ。(「幅優先」という表現が合っているか微妙だが)

Haskell
repeat_combination :: [Int] -> Int -> [[Int]]
repeat_combination xs 0 = [[]]
repeat_combination xs n = [ x : y | x <- xs, y <- repeat_combination xs (n-1)]
Clojure
(defn repeat-combination [xs n]
  (if (= n 0)
    [[]]
    (for [x xs
          y (repeat-combination xs (dec n))]
       (cons x y))))

上記は、組み合わせた結果の帰り値に対して、さらに組み合わせを計算する。

末尾最適化可能なやり方

同じ幅優先だが、こちらは引数に結果を渡すやり方で、これだと末尾最適化できる。

Haskell
combination :: [Int] -> [[Int]] -> Int -> [[Int]]
combination xs ys 0 = ys
combination xs ys n = combination xs [ x : y | x <- xs, y <- ys ] (n-1)

repeat_combination :: [Int] -> Int -> [[Int]]
repeat_combination xs n = combination xs [[]] n
Clojure
(defn combination [xs ys n]
  (if (= n 0)
    ys
    (recur xs
           (for [x xs, y ys] (cons x y))
           (dec n))))

(defn repeat-combination [xs n]
  (combination xs [[]] n))
深さ優先で組み合わせる場合

これも引数に結果を渡して繰り返すやり方。

Haskell
combination xs ys 0 = [ys]
combination xs ys n = concat [combination xs (ys++[x]) (n-1) | x <- xs]

repeat_combination :: [Int] -> Int -> [[Int]]
repeat_combination xs n = combination xs [] n
Clojure
(defn combination [xs ys n]
  (if (= n 0)
    [ys]
    (apply concat
           (for [x xs] (combination xs (conj ys x) (dec n))))))

(defn repeat-combination [xs n]
  (combination xs [] n))

concatが美しさを損ねているが、まあしょうがない・・・。


ひとつ選ぶとしたら、分かりやすさと簡潔さ、プラスStack Overflowにならないので、2番目のやり方かなあ。

Clojureで日付の計算をする

引き続き「プログラマ脳を鍛える数学パズル」の問題を解いて遊んでいる。 第7問は日付を扱う。 問題自体は簡単なのだが、Clojureでの日付の扱い方がよく分からなくて、調べるのに時間がかかった。

clj-timeというライブラリがあるようだが、わざわざな・・・。

結局javaライブラリを生でたたくのが一番で、しかしまあオブジェクト指向APIは何かするのにいちいち面倒いこと。 もう一度面倒くさいことをしなくて済むようにメモを残しておこう。

動くコードを残しておくのが一番手っ取り早い。

処理

"19991225" から10日分の年月日を出力する

コード
(ns prog-math-puzzle.test-date
  (import (java.util Calendar)
          (java.text SimpleDateFormat)))

(def date-format (SimpleDateFormat. "yyyyMMdd"))

(defn date [dstr]
  (let [cal (Calendar/getInstance)]
    (.setTime cal (.parse date-format dstr))
    cal))

(defn to-str [cal]
  (.format date-format (.getTime cal)))

(defn next-day [cal]
  (let [nc (.clone cal)]
    (.add nc Calendar/DATE 1)
    nc))

(defn date-seq [cal]
  (lazy-seq (cons cal (date-seq (next-day cal)))))

(println 
  (map to-str (take 10 (date-seq (date "19991225")))))
出力

(19991225 19991226 19991227 19991228 19991229 19991230 19991231 20000101 20000102 20000103)

メモ

必要なライブラリ

java.util.Calendarjava.text SimpleDateFormat

日付のフォーマット

(def date-format (SimpleDateFormat. "yyyyMMdd")) の部分で、"yyyy-mm-dd"とかでもOK。

日付オブジェクトの生成

java.util.Calendarオブジェクトを作る。

(defn date [dstr]
  (let [cal (Calendar/getInstance)]
    (.setTime cal (.parse date-format dstr))
    cal))

.setTimejavaのメソッド呼び出しなので、返り値にデータを返す訳ではなくて、calを書き換えちゃうんだな。 なので、最後にcalを返している。

また、javaのメソッドで日付データを変える場合は、データをコピーしてから、やらないといけない。 元のデータが書き換わっちゃうから。

next-day関数ではCalendarインスタンスcloneしてから、日にちを1つ足している。

(defn next-day [cal]
  (let [nc (.clone cal)]
    (.add nc Calendar/DATE 1)
    nc))

以上。

Haskell/Clojureでrepeated_combinationを実装してみる

前回やった Haskell/Clojureで数学パズル:コインの両替 - Programmer's Note の問題5は、書籍の解答例のひとつに、Rubyのrepeated_combination()を使った解があった。

こいつは任意の回数、配列の要素の組み合わせを出してくれる関数で、 探せばClojure/Haskellにもあるだろうけど、ちょうどいい感じの題材なので実装してみる。

任意の大きさのリスト[a,b,c,d,...]を任意の回数n、各要素の組み合わせを出す。

使い方
repeat_combination [1 2 3] 2
; -> ((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))

repeat_combination [1 2 3] 3
; -> ((1 1 1) (1 1 2) (1 1 3) (1 2 1) (1 2 2) (1 2 3) (1 3 1) (1 3 2) (1 3 3) (2 1 1) (2 1 2) (2 1 3) (2 2 1) (2 2 2) (2 2 3) (2 3 1) (2 3 2) (2 3 3) (3 1 1) (3 1 2) (3 1 3) (3 2 1) (3 2 2) (3 2 3) (3 3 1) (3 3 2) (3 3 3))

アルゴリズムは2通りあって、深さ優先か幅優先か。

いろいろやってみたけれど、下記の実装が一番シンプルでわかりやすいな。 幅優先で処理するやり方。

Haskellの実装:

comb :: [[Int]] -> [[Int]] -> [[Int]]
comb xs ys = [ x ++ y | x <- xs, y <- ys]

comb_n_times :: [[Int]] -> Int -> [[Int]]
comb_n_times xs 1 = xs    
comb_n_times xs n = comb xs (comb_n_times xs (n-1))

repeat_combination :: [Int] -> Int -> [[Int]]
repeat_combination xs 1 = [xs]
repeat_combination xs n = let ys = [[x] | x <- xs] 
                          in comb_n_times ys n

やっていることは以下のような感じ。

入力データを変換してから
[a,b,c] => [[a],[b],[c]]

1回目
[[a],[b],[c]] x [[a],[b],[c]]
  => [a,a][a,b][a,c][b,a][b,b][b,c][c,a][c,b][c,c]

2回目は1回目の結果にたいして、
[[a],[b],[c]] x [[a,a][a,b][a,c][b,a][b,b][b,c][c,a][c,b][c,c]]
  => [a,a,a][a,a,b][a,a,c] ....

以上を繰り返す

コードとしては分かりやすいが、SICPでいうrecusive processになっているので、末尾最適化できない。 nが大きいとStack Overflowを起こす。 とはいえ、この幅優先な方法は、iterative processな実装も可能ではある。

深さ優先

一方、深さ優先で組み合わせを作っていくやりかたもある。 プロセスはこんな感じ。

[a,b,c] x [a,b,c] x [a,b,c]

 a -> a -> a  => [a,a,a]
        -> b  => [a,a,b]
        -> c  => [a,a,c]
   -> b -> a  => [a,b,a]
        -> b  => [a,b,b]
        -> c  => [a,b,c]
 ...

こっちの方はClojureの実装を載せる。

(defn repeat-combination [xs n]
  (letfn [(comb-depth [cnt res]
            (if (zero? cnt)
              [res]
              (apply concat
                     (for [x xs]
                       (comb-depth (dec cnt)
                                   (conj res x))))))
          ]
    (if (= n 1)
      [xs]
      (comb-depth n []))))

こっちの方法はあまりメリットはないかな・・・。 iterative processな実装にすることができない(たぶん)。

Haskell/Clojureで数学パズル:コインの両替

いやあ「プログラマ脳を鍛える数学パズル」楽しいですわ。 まだ5問しかやっていないけど、Clojure/Haskell両方で解いているので、一粒で二度美味しい。 しかも、解説は違う視点の解法を示してくれるので、3度も4度も美味しい感じだ。

5問目は、お金の両替問題で、これシンプルだけど奥が深い。 1000円を10円、50円、100円、500円に両替する。同じコインは何枚使ってもいいが、最大コイン数は15枚。 この時の両替パターン数を求める。

名著SICPにも内容が少し違う両替問題が出ていて、再帰の威力を見せつけられたな。

さて、この問題、まず最初にぱっと思いつく方法は、ベタに組み合わせと条件判定。

Haskellの回答例は、

change_coin :: Int -> Int -> Int
change_coin money max_coins = 
    sum [1 | m10 <- [0..max_coins],
             m50 <- [0..max_coins],
             m100 <- [0..max_coins],
             m500 <- [0..max_coins],
             m10 + m50 + m100 + m500 <= max_coins,
             money == (10*m10 + 50*m50 + 100*m100 + 500*m500)]

main :: IO ()
main = do print $ change_coin 1000 15 

リスト内包表記、便利で簡潔で美しいですわ。

似た簡潔さでClojureも書ける。for文を使う。

(defn change_coin [money max_coins]
  (reduce +
          (for [m10 (range 0 (inc max_coins))
                m50 (range 0 (inc max_coins))
                m100 (range 0 (inc max_coins))
                m500 (range 0 (inc max_coins))
                :when (and (<= (+ m10 m50 m100 m500) max_coins)
                           (= money (+ (* 10 m10)
                                       (* 50 m50)
                                       (* 100 m100)
                                       (* 500 m500))))
                ]
            1)))

(println (change_coin 1000 15))

少しだけ考えて、再帰を使って汎用的な関数を作ってみる。

Haskell版:

change_coin :: Int -> [Int] -> Int -> Int
change_coin 0 _ _ = 1
change_coin _ _ 0 = 0
change_coin _ [] _ = 0
change_coin money (x:xs) max_coins
    = sum [ change_coin (money - x * use) xs (max_coins - use)
            | use <- [0..max_coins]]

main :: IO ()
main = do print $ change_coin 1000 [10,50,100,500] 15

考え方としては、使うコインのリスト[10,50,100,500]を与えて、前からコインを取り出して、 (この場合だとまずは10円)

  • コインを0枚使う → 1000-0 に対して残ったコインで両替する
  • コインを1枚使う → 1000-10 に対して残ったコインで両替する
  • ・・・
  • コインを15枚使う → 1000-10*15 に対して残ったコインで両替する

というのを再帰でやる。(まあ15枚使ったら、もう終わりだけどね) 最後に残金が0なら、うまく換金できたので1を返し、 それ以外でコインのリストが空になったり、最大コイン数使ったら0を返す。

Clojureも同じように組める。

(defn change_coin_patterns [money coins max-coins]
  (cond (zero? money) 1
        (empty? coins) 0
        (zero? max-coins) 0
        :else (reduce + 
                      (for [uses (range 0 (inc max-coins))]
                        (change_coin_patterns (- money (* uses (first coins)))
                                              (rest coins)
                                              (- max-coins uses))))))

(println (change_coin_patterns 1000 [10 50 100 500] 15))

Haskellだとパターンマッチングを使った記述がビューティフル。

Haskell/Clojureで数値をN進数表記に変換

去年からHacker Rankが面白くてハマっている。 今年に入ってからHaskellを始めたので、ますます関数型プログラミングアルゴリズムをやりたい気分が上がっている。

アルゴリズム勉強したいなと思い、 有名なKnuth先生の「The Art of Computer Programming」を買って、 ちょっと読んでみたら、これアセンブラなんですね。興味を削がれたのでそっと積んで置く・・・。

一方、Hacker Rankに飽き足らず、コードパズル系の本も気になっていて、 「プログラマ脳を鍛える数学パズル」も買ってみた。書籍だと解説もあるので楽しみである。

早速、しょっぱなの2問をやってみた。問題自体はいいのだが、 回答がプログラミング言語の機能をばんばん使う前提にしているんだな。 (rubyのevalレベルまで使っていいとは)

制限時間が設定されていて、とにかく速く問題を解くことに目が置かれているので、 そうしているんだな。

別にいいんだけど、 しかしまあ、美味しい部分は、その端折ったところにあったりする。

1問目は、同じ整数を表す10進・8進・2進表記が回文になっている数を求める問題なのだが、 N進数に変換する部分はプログラミング言語のライブラリを使っていい前提だ。

・・・このN進数表記に変換する部分が美味しい部分ですやん。

実際、Clojure, Haskellで書いてて面白く楽しかった部分だ。 やっていること自体は難しくないが、最大公約数を求めるユークリッドの相除法みたく、 数学に近い部分の本質的な面白さがある。

これは、関数型言語で書くと短くて鑑賞のしがいのあるコードが書ける。 (最近はコードを書いて悦悦と眺めるのが目的みたいな感じになっている。 そのために良問を探している感がある。)

さて、ある数をN進表記に変換する関数を、まずはHaskellで書いてみる。

どんな関数かというと、整数10を2進表記に変換する場合に、

Prelude > n_ary_str 10 2
"1010"

という風に使う関数だ。

import Data.Char

n_ary :: Int -> Int -> [Int]
n_ary 0 _ = []
n_ary num base = n_ary quotient base ++ [remainder]
                 where
                    quotient = num `quot` base
                    remainder = num `mod` base

n_ary_str :: Int -> Int -> String
n_ary_str num base = map intToDigit (n_ary num base)

やっていることは、 まずN進の数字のリストを求めて、それを文字列にしている。

n_ary 10 2[1, 0, 1, 0] というリストが返る。 これを使ってn_ary_str関数で、順に文字に置換しているだけだ。 Haskellの文字列は文字の配列なので、置換したら終わり。

10進以上は対応していないが、対応するのは簡単だ。

たとえばn_ary 199 16[12, 7]になるが、これを['C', '7']に変換するだけだ。 つまり、10以上の数字を'A'からのアルファベットに置き換えるだけ。

Haskellは習い始めだが、whereというシンタックスはえらく感動する。 これを使うとコードの本質的な部分を先に書けて意図を強調できる。

上記コードは、別に使わなくてもいいのに、わざわざwhereを使っているが、 結局N進数って何?という問いに対して、ソースコードで、 「Nで割った余りを求める。自分の上の桁に対して商を与えそれを繰り返す」です、と表現できる。 (Nに相当する部分がソースではbase

Haskellは本当にそのまま定義を書ける感じだ。大学の授業とかで使って欲しい言語No.1だな。

Clojureも同じように書ける。(n_ary関数だけ)

(defn n_ary [number base]
  (if (zero? number)
    []
    (let [quotient (quot number base)
          remainder (mod number base)]
    (conj (n_ary quotient base) remainder))))

たぶんLISPerはこんな冗長なコードは書かない(笑。

自分のいつものClojureのコードだと下記のようになる。(文字列変換も込みで)

(defn n_ary [number base] 
  (loop [n number,
         res []]
    (if (zero? n)
      res
      (recur (quot n base)
             (cons (mod n base) res)))))

(defn n_ary_str [number base]
  (apply str (n_ary number base)))

Clojureのloopマクロは本当に便利で多用している。 すごく便利なのだが、実は初見だとコードがわかりづらいかもしれないね。

Haskellの勉強をはじめる

今年に入ってからHaskellを勉強し始めた。これが結構楽しい。教科書は「Programming in Haskell」。(この本は名著だ)

読み進めてコードを書いてみるにつれ、最初の想像と違って、かなりLISPに近い印象を受ける。ラムダ計算がベースなので、そっくりなのは当たり前かもしれない。

この言語の文法は可能な限り簡略化されてて、関数の定義にdefもカッコも必要なく、引数を与えるのにカンマもいらない。

手書きでアルゴリズム考えるのにLISPより使いやすい。カッコ不要で中置記法、条件文も明瞭で無駄がなく、コードが読みやすい。教育用としてとても使いやすい言語だと思う。(そのために設計されたのかもしれないが)

LISPのS式とは違った美しさがある。

かなり好きになりそう。

この先、興味があるのは、型がプログラミング上どれくらい本質的な重要性を持つかというところ。そもそもHaskellを勉強してみたくなったのは、Rich Hickeyが静的型とパターンマッチングをdisってたのが気になったからだしな。

最近はClojureでHacker Rankの問題を解いてて、すっかり考え方(解き方)がマンネリ化してきていると感じている。再帰は手軽な(loop...)ばかり使ってしまう。まあ得意技を持つのは悪いことではないが、引き出しの数が増えない。

Haskellの勉強はかなり良い意味で視点の転換、拡張をさせてくれている。

例えばリスト内包表記はClojureの(for...)と実質同等なのだが、処理対象をデータグループとして捉えるか、forループの結果として捉えるかで、問題の解き方が大きく違ってくるんだなと気付かされた。(本の中でこの違いを言及している訳じゃなくて、自分が後者の視点ばかり持っていたから、前者の視点での解法にinsightを与えられた)

文法の違いが実は思考の展開の違いを生んでいる。

 

「達人プログラマ」がいう年に一個新しい言語を学べというのは、侮れないアドバイスなり。と。