トップ > Haskell > 「Write Yourself a Scheme in 48 Hours」 を写経してみる(10) : cdr の評価が間違っている。

「Write Yourself a Scheme in 48 Hours」 を写経してみる(10) : cdr の評価が間違っている。

Haskell scheme

「Write Yourself a Scheme in 48 Hours」 を写経してみる(6) : 評価その２の中で cdr を評価する部分があったのですけれども、kazu-yamamoto さんの「HaskellでScheme」という記事の中で「cdr の定義が間違っている」記述を見つけました。

cdr [DottedList (_ : xs) x] = return $ DottedList xs x
cdr [DottedList [xs] x] = return x

は誤りで、正しくは以下ということです。

cdr [DottedList [xs] x] = return x   -- cdr [DottedList [_] x] = return x の方が分かりやすい。
cdr [DottedList (_ : xs) x] = return $ DottedList xs x

何が違うのかというとパターンマッチする順序です。下段にマッチを期待しているのに先に上段にマッチしてしまいます。

-- NG
$ rlwrap runghc listing8.hs
Lisp>>> (cdr '(a . b))
-- > ( . b)               -- DottedList [] (Atom "b") : 内部表現

-- 正しくはこうなるべきです。
-- > b                    -- Atom "b" : 内部表現

-- 次の場合は問題ありません。
Lisp>>> (cdr '(a b . c))
-- > (b . c)              -- DottedList [Atom "b"] (Atom "c") : 内部表現
Lisp>>> quit

修正後は問題ありません。

-- OK
Lisp>>> (cdr '(a . b))
b   -- Atom "b"

Lisp>>> (cdr '(a b . c))
(b . c) -- DottedList [Atom "b"] (Atom "c")

どのように誤動作したのか確認してみます。

  • (cdr '(a . b)) の内部表現は次のようなものです。
> readExpr "(cdr '(a . b))"
Right (List [Atom "cdr",List [Atom "quote",DottedList [Atom "a"] (Atom "b")]])
  • cdr を評価する段階では quote が既に評価されています。
> readExpr "(cdr (a . b))"
Right (List [Atom "cdr",DottedList [Atom "a"] (Atom "b")])


-- (1) cdr [DottedList (_ : xs) x] = return $ DottedList xs x
-- (2) cdr [DottedList [xs] x] = return x
  • [DottedList [Atom "a"] (Atom "b")] を (1) にマッチさせるとどうなるか。
> let [DottedList (_ : xs) x] = [DottedList [Atom "a"] (Atom "b")]
> xs   --> []
> x   -- > Atom "b"
  • DottedList [] (Atom "b") の show は "( . b)"となります。
> showVal (DottedList [] (Atom "b")) -- > "( . b)"
  • (2) にマッチすれば x だけ使用されますので問題ありません。
> let [DottedList [_] x]=[DottedList [Atom "a"] (Atom "b")]
> x  -- > Atom "b"
> showVal (Atom "b") -- > "b"
  • (cdr (a b . c)) の場合は問題ありません。
> readExpr "(cdr (a b . c))"
Right (List [Atom "cdr",DottedList [Atom "a",Atom "b"] (Atom "c")])