hippos-lab::blog

どうにかこうにか読み進めてきた「Programing in Haskell」Chapter8 8.4 Sequencingで躓いてます。文字列の1番目と3番目の文字でペアを作成するというサンプルなんですがうまくいきません。実行例は次の通りです。

> parse p "abcdef"
[(('a','c'),"def")]

本書で、示されている定義は(前段からの続きも含めて）次のようになっています。

type Parser a = String -> [(a,String)]

return :: a -> Parser a
return v = \inp -> [(v,inp)]

item :: Parser Char
item = \inp -> case inp of
               [] -> []
               (x:xs) -> [(x,xs)]

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = \inp -> case parse p inp of
                 [] -> []
                 [(v,out)] -> parse (f v) out

parse :: Parser a -> String -> [(a,String)]
parse p inp = p inp

p :: Parser (Char,Char)
p = do x <- item
       item
       y <- item
       Main.return (x,y)

ここで、最後のpの定義で怒られます。

Couldn't match expected type `Char'
against inferred type `[(Char, String)]'
Expected type: [((Char, Char), String)]
Inferred type: [(([(Char, String)], [(Char, String)]), String]

pの型はParser (Char,Char)、つまりString -> [(Char,Char),String]なのに対して、xやyは[(Char,String)]なので、"Main.return (x,y)"はおかしいよって言われています。実行例から類推すると、

parse p "abcdef"
-- x < item  x = [('a',"bcdef")]
item "abcdef"
-- item                  [('b',"cdef")] 
item "bcdef"
 -- y < item  y = [('c',"def")]
item "cdef"
-- Main.return (x,y) ????
(Main.return ('a','c')) "def" 

という流れだと思うのですが、そもそもdo式で2回目以降のitemに適用する引数がどこからくるのかよくわかりません。この前段ででてくる(>>=)が関係しているような気がするのですが、その定義は、

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = \inp -> case parse p inp of
                 [] -> []
                 [(v,out)] -> parse (f v) out

で、[(v,out)] -> parse (f v) outですからこの章までの定義ではMain.returnしか適用できない気がします。実際に単独で実行してみたら、

> parse (item Main.>>= Main.return) "abcdef"
[('a',"bcdef")]
> parse (item Main.>>= item) "abcdef"
    Couldn't match expected type `Char' against inferred type `[Char]'
      Expected type: Char
      Inferred type: String
    In the second argument of `(Main.>>=)', namely `item'
    In the first argument of `parse', namely `(item Main.>>= item)'

とエラーになり、itemは連続して適用できませんでした。do式のようにitemを連続して適用するための定義を

(>>=) :: Parser a -> Parser b -> Parser b
p >>= f = \inp -> case parse p inp of
                    [] -> []
                    [(v,out)] -> parse f out

と修正すれば、

>parse (item Main.>>= item Main.>>= item) "abcdef"
[('c',"def")]

と、なるのでdo式でitemを3回繰り返したのと同じになるかと思うのですが、結局でているエラーはp::Parser (Char,Char)と、Main.return (x,y)は型が違うよっていうエラーには関係なさそう。

なんとか、Main.return (x,y)の前にx/yがCharになるような"fst ((!!) x 0)"みたいなマジックをどこかに仕込まなければいけないんだと思うのですが....

Chapter8 になって、(>>=)とreturnがでてきたあたり、とうとうアレなんでしょうか？まだHaskellを勉強し始めて日が浅く、テキストはこの「Programming in Haskell」しか読んでいないのですが、Haskellを学ぶにあたってはアレが鬼門だということはチラチラ聞こえています。一日考えて頭がごちゃごちゃになったので整理するつもりでこのエントリを書いてみたのですが、さらに混乱してきたのでとりあえずここまで。そろそろ英語だけのテキストだと限界かなぁーという気も少ししてきました。この本はどうも大学のテキストらしく基本的な知識のある人を対象にしているみたいだし、僕の英語力ではなんか大切なこと読み落としている気がします。