2017-12-26

Haskellでwordsを実装してみた

Haskellを学び始めたが、いまだにまともなコードを書くことができないでいる。理由は簡単で、まだ標準入出力が扱えないからだ。

標準入出力はUNIXでは極めて根本的な機能だ。標準入出力が扱えるようになればだいたいの処理はできると考えてよい。というのも、UNIXではパイプによって標準入出力の入力元と出力先を変えることができるからだ。パイプを使えば、ファイル操作やネットワーク操作をコードで表現する方法を知らなかったとしても、操作ができるようになる。

ところが、Haskellでは標準入出力を扱えるようになるまでが遠い。別に書けないわけではない。今でもHaskellでHello,Worldぐらい書けるし、特定の処理がしたいのであれば似たような入出力処理をするコードをどこからか探してきて改変することで目的のコードを作り出すことはできる。そういう意味では、現時点でもHaskellである程度のコードは書けるだろう。しかし、それでは言語を真に理解したことにはならない。言語の仕様を理解し、他人の書いたコードの改変ではなく、自分でコードを無から書けてこそ、自由自在のプログラミングが可能になる。

しかし、関数型言語であるHaskellでは入出力などという副作用を伴う処理には特別な配慮が必要らしく、いまだに標準入出力にたどり着いていない。

しかし、今までに学んだHaskellの知識を使って自力で何かを実装してみたいので、今回はwordsを実装することにした。

wordsは文字列を空白文字を区切り文字として分割した文字列のリストを返す。

> words "aaa bbb ccc"
["aaa","bbb","ccc"]

処理自体は簡単なはずなのだが、これをHaskellの流儀でやるのは割とだるい。アルゴリズム自体はすぐに思い浮かんだのだが、実際にコードを書くと、様々な問題に悩まされた。

takeWord s = takeWhile (not . isSpace) $ dropWhitespace s
dropWhitespace s = dropWhile isSpace s

words' [] = []
words' s =
    let
        word = takeWord s
        rest = drop (length word) $ dropWhitespace s
    in
        word:(words' rest) 

アルゴリズムとしては、文字列の先頭から連続する空白文字をdropし、空白文字が現れるまでtakeし、今回の処理した文字列分dropし、再帰する。

これで使った関数も実装してみた。

takeWhile' _ [] = []
takeWhile' f (x:xs) =
    if f x
    then x: takeWhile' f xs
    else []

dropWhile' _ [] = []
dropWhile' f p@(x:xs) =
    if f x
    then dropWhile' f xs
    else p

drop' _ [] = []
drop' n x | n <= 0 =  x
drop' n (_:xs) = drop' (n-1) xs

length' [] = 0
length' (x:xs) = 1 + length' xs

not' True = False
not' False = True

ちなみに、模範解答はghc/libraries/base/data/OldList.hsにある。

words s                 =  case dropWhile {-partain:Char.-}isSpace s of
                                "" -> []
                                s' -> w : words s''
                                      where (w, s'') =
                                             break {-partain:Char.-}isSpace s'

なるほどbreakは面白い仕組みだ。文字列の切り出しと文字列の先頭のdropを同時にやれるのでコードがきれいになる。早速実装してみよう。

break' _ [] = ( [],[] )
break' f p@(x:xs) =
    if f x
    then ( [], p )
    else let ( a, b ) = break' f xs
         in ( x:a, b )

模範解答。

break                   :: (a -> Bool) -> [a] -> ([a],[a])
#if defined(USE_REPORT_PRELUDE)
break p                 =  span (not . p)
#else
-- HBC version (stolen)
break _ xs@[]           =  (xs, xs)
break p xs@(x:xs')
           | p x        =  ([],xs)
           | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
#endif

USE_REPORT_PRELUDEは、Haskellの仕様書であるHaskell Reportの定義どおりの実装だ。Haskell Reportの定義は効率ではなく正しさだけを目的としている。通常はUSE_REPORT_PRELUDEではない方が使われる。

ところで、"break _ xs@[] = (xs,xs)"は、"break _ [] = ([],[])"と書くのと変わりがないと思うのだが、何か違いがあるのだろうか。

さて、ここまで何の問題もなく実装できているように見えるが、実際は些細な間違いで何時間も悩んでいる。

最初に書いたwords'は以下のような間違った結果を返した。

> words' "aaa bbb  ccc"
["aaa", "bbb", "b", "ccc", "cc"]

これはなぜかと言うと、処理した文字列を切り取る処理が以下のようになっていて、空白文字分を考慮していなかったからだ。

rest = drop (length word) s

しかし問題の原因を特定するのには苦労した。標準入出力が使えないので、最も原始的なprintfデバッグすらまだ使えないためだ。traceというものはあるが、問題はtraceの評価も実際に評価したときにしか行われず、現時点でHaskellのコードを評価する方法として、GHCiに食わせて表示させるということぐらいしか知らないため、traceの出力と本来の出力がごちゃまぜになって極めてわかりにくい。

もう一つハマった落とし穴は、dropWhileを実装していたときだ。以下のように間違ったコードを書いてしまった。

dropWhile' _ [] = []
dropWhile' f p@(x:xs) =
    if f x
    then dropWhile' xs
    else p

間違っている場所がわかるだろうか。私はわからない。GHCのエラーメッセージは型が違うということは知らせてくれるが、具体的にどこのコードが期待している型が違うのかということは教えてくれない。GHCが指し示す問題のある行は、"dropWhile' f p@(x:xs) ="だ。しかし、問題は"then dropWhile' xs"にあるのだ。エラーメッセージは、dropWhile'の型は(t -> Bool) -> [t] -> [t]だが、[t] -> [t]として使おうとしてエラーになっていることを教えてくれる。そこまで分かっているのならば、[t] -> [t]としてdropWhile'を使おうとしている箇所を教えてくれたっていいだろう。技術的にできるはずなのに、なぜか教えてくれない。

Haskellの実装であるGHCのエラーメッセージはあまりにも不親切すぎる。

7 comments:

  1. ちなみに、本当の意味で入出力処理を扱えるようになるのはconduitライブラリを覚えた後だ

    ReplyDelete
  2. 定義が間違っていた場合呼び出しが間違っていると指摘されるのは混乱の元だ

    ReplyDelete
  3. 入出力だけならIOでハンドルつかって手続きを書くだけ
    ただ問題は、Haskellらしくやるにはさらにpipesやconduitなどのストリーム処理ライブラリを覚える必要があることだ
    これらは、(言語内で標準入出力を利用するかの如く)ストリームからの入出力操作だけを行えるモナディックなインターフェイスを提供する。これを用いることで例えば入力が標準入力だろうがプログラム中で行われたファイル読み込みだろうがリストだろうがポリモーフィズムに扱うことができる

    わざわざ複数種類があるのはインターフェイスや実装の思想的な違いや機能性、速度で差があるからだな・・・ここら辺Haskellはまだまだ思想的にもライブラリ実装的にも発展途中という印象

    ReplyDelete
  4. あと、関数型のデバッグするならインタプリタに関数の一部分だけ取り出して引数を与えREPLするのがはやい
    手続き型と違ってHaskellは参照透過性があるのが売りなので関数に与えている値一つ一つを取り出してどう動作しているかテストすることができるのでprintfデバッグよりどこでエラーが出たのか問題を分割して実行していくのが早い REPLとエディタを並べておくと便利

    ReplyDelete
  5. ghc-8.2からエラーメッセージが親切になっているのでそちら使ってください。
    lts-10.0からghc-8.2です。

    ReplyDelete
  6. 以下のようにdropWhile'の型を明示すれば意図するエラーが出るはずです。
    型推論にも限界はあるので、関数を定義するときは意識的に型を書きます。

    ```
    dropWhile' :: (t -> Bool) -> [t] -> [t] -- 型の明示
    dropWhile' _ [] = []
    dropWhile' f p@(x:xs) =
      if f x
        then dropWhile' xs -- 確認のため間違っておく
        else p
    ```

    ----- 型を指定しない場合 -----
    dropWhile.hs:1:1: error:
      • Couldn't match type ‘a -> Bool’ with ‘[a]’
        Expected type: [a] -> [a]
         Actual type: (a -> Bool) -> [a] -> [a]
      • Relevant bindings include
         dropWhile' :: [a] -> [a] (bound at dropWhile.hs:1:1)
     |
    1 | dropWhile' _ [] = []
     | ^^^^^^^^^^^^^^^^^^^^...
    -------------------------

    ----- 型を指定した場合 -----
    dropWhile.hs:5:14: error:
      • Couldn't match expected type ‘[t]’
              with actual type ‘[t0] -> [t0]’
      • Probable cause: ‘dropWhile'’ is applied to too few arguments
       In the expression: dropWhile' xs
       In the expression: if f x then dropWhile' xs else p
       In an equation for ‘dropWhile'’:
         dropWhile' f p@(x : xs) = if f x then dropWhile' xs else p
      • Relevant bindings include
        xs :: [t] (bound at dropWhile.hs:3:19)
        x :: t (bound at dropWhile.hs:3:17)
        p :: [t] (bound at dropWhile.hs:3:14)
        f :: t -> Bool (bound at dropWhile.hs:3:12)
        dropWhile' :: (t -> Bool) -> [t] -> [t] (bound at dropWhile.hs:2:1)
     |
    5 | then dropWhile' xs
     | ^^^^^^^^^^^^^

    dropWhile.hs:5:25: error:
      • Couldn't match expected type ‘t0 -> Bool’ with actual type ‘[t]’
      • In the first argument of ‘dropWhile'’, namely ‘xs’
        In the expression: dropWhile' xs
        In the expression: if f x then dropWhile' xs else p
      • Relevant bindings include
         xs :: [t] (bound at dropWhile.hs:3:19)
         x :: t (bound at dropWhile.hs:3:17)
         p :: [t] (bound at dropWhile.hs:3:14)
         f :: t -> Bool (bound at dropWhile.hs:3:12)
         dropWhile' :: (t -> Bool) -> [t] -> [t] (bound at dropWhile.hs:2:1)
     |
    5 | then dropWhile' xs
     | ^^
    ------------------------

    ReplyDelete


  7. Thank you so much for sharing this great blog.Very inspiring and
    helpful too.Hope you continue to share more of your ideas.
    I will definitely love to read.

    Here's my website : -- 안마

    (freaky)

    ReplyDelete

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.