|
リストの比較以外、これらの殆どは自明です。これはリストが同じ長さかどうか確かめた後、2つのリストを[http://www.haskell.org/onlinereport/standard-prelude.html#$vzip zip]し、[http://www.haskell.org/onlinereport/standard-prelude.html#$vall all]を使ってどれか一つでも<code>eqvPair</code>が偽を返すペアがあれば偽を返すようにします。<code>eqvPair</code>は局所的定義の一例です。それは<code>where</code>を使って定義され、普通の関数のように働きますが、<code>eqv</code>のその節のその部分のみで有効です。<code>eqv</code>は引数の数が2である限りエラーを投げないので、<code>Left err -> False</code>が実行されることはありません。
== Equal? and Weak Typingと弱い型付け: Heterogenous Lists異型リスト ==
以前私たちは弱い型付けを導入したので、型を無視して2つの値が同じと解釈できるかどうか見る<code>equal?</code>関数を実装します。例えば、<code>(eqv? 2 "2") => #f</code>ですが、<code>(equal? 2 "2") => #t</code>であって欲しいのです。基本的には、unpack関数全てを試してみて、その中のどれかがHaskell的に等しければ真を返すようにします。
Since we introduced weak typing above, we'd also like to introduce an equal? function that ignores differences in the type tags and only tests if two values can be interpreted the same. For example, <span class="inline_lisp">(eqv? 2 "2") = #f</span>, yet we'd like <span class="inline_lisp">(equal? 2 "2") = #t</span>. Basically, we want to try all of our unpack functions, and if any of them result in Haskell values that are equal, return true.
明らかな方法は、unpack関数をリストに格納して<code>mapM</code>を使ってそれらを順に実行するというものですが、残念ながら、これは上手くいきません。なぜなら、標準ではHaskellはリストは''同じ型の''ものしか含むことができないからです。色々なunpack関数は違った型の値を返すので、同じリストにしまうことはできません。
The obvious way to approach this is to store the unpacking functions in a list and use mapM to execute them in turn. Unfortunately, this doesn't work, because standard Haskell only lets you put objects in a list ''if they're the same type''. The various unpacker functions return different types, so you can't store them in the same list.
ここでは型クラスによって制約される異型リスト(heterogeneous list)を作るために存在型というGHCの拡張を使うことでこの問題を回避します。Haskellでは言語拡張はとてもありふれたことです。言語拡張はそれなりに大きなプログラムを書くときには事実上必須で、しばしば異なる実装間で互換性があります(存在型はHugsとGHCの両方で動き、標準化の候補です)。
We'll get around this by using a GHC extension - [[Haskell/Existentially quantified types|Existential Types]] - that lets us create a heterogenous list, subject to typeclass constraints. Extensions are fairly common in the Haskell world: they're basically necessary to create any reasonably large program, and they're often compatible between implementations (existential types work in both Hugs and GHC and are a candidate for standardization).
最初にやらなければならないのは、<code>LispVal -> 何か</code>という関数において、その「何か」が同値性をサポートしていればどんなものでも保持することのできる型を定義することです。
The first thing we need to do is define a data type that can hold any function from a LispVal -> something, provided that that "something" supports equality:
<syntaxhighlight lang="haskell">
data Unpacker = forall a. Eq a =>> AnyUnpacker (LispVal ->> ThrowsError a)
</syntaxhighlight>
これは、型の制約を除けば、普通の代数的データ型と同じようなものです。上の定義は「<code>Eq</code>のインスタンスであるどんな型についても、<code>LispVal</code>からその型への関数で、エラーを投げるかもしれないものから<code>Unpacker</code>を定義することができる」と言っています。<code>AnyUnpacker</code>で関数をラップしなければなりませんが、そうすれば私たちは<code>Unpacker</code>のリストを作ることができ、やりたかったことができるようになります。
This is like any normal algebraic datatype, except for the type constraint. It says, "For any type that is an instance of Eq, you can define an Unpacker that takes a function from LispVal to that type, and may throw an error". We'll have to wrap our functions with the AnyUnpacker constructor, but then we can create a list of Unpackers that does just what we want it.
<code>equal?</code>に直接取り掛かるのではなく、まずunpackerを取ってそれがunpackする2つの<code>LispVal</code>が等しいかどうか判断するヘルパー関数を定義しましょう。
Rather than jump straight to the equal? function, let's first define a helper function that takes an unpacker and then determines if two LispVals are equal when it unpacks them:
<syntaxhighlight lang="haskell">
unpackEquals :: LispVal ->> LispVal ->> Unpacker ->> ThrowsError Bool
unpackEquals arg1 arg2 (AnyUnpacker unpacker) =
do unpacked1 <<- unpacker arg1
unpacked2 <<- unpacker arg2
return $ unpacked1 == unpacked2
`catchError` (const $ return False)
</syntaxhighlight>
After pattern-matching to retrieve the actual function, we enter a 実際の関数を得るためにパターンマッチした後、<code>ThrowsError</code>モナドのためのdo-block for the ThrowsError monad. This retrieves the ブロックに入ります。ここで<code>LispVal</code>からHaskell values of the two LispVals, and then tests whether they're equal. If there is an error anywhere within the two unpackers, it returns false, using the の値を取り出し、それらが等しいかどうか調べます。もしその過程のどこかでエラーが起これば、[http://www.haskell.org/onlinereport/standard-prelude.html#$vconst const] function because を使って偽を返します。<code>const</code>を使うのは[http://www.haskell.org/ghc/docs/latest/html/libraries/mtl/Control-Monad-Error.html catchError] expects a function to apply to the error value.がエラーに適用する関数を求めているからです。
最後に、<code>equal?</code>をこれらの補助関数を使って定義します。
Finally, we can define equal? in terms of these helpers:
<syntaxhighlight lang="haskell">
equal :: [LispVal] ->> ThrowsError LispVal
equal [arg1, arg2] = do
primitiveEquals <<- liftM or $ mapM (unpackEquals arg1 arg2)
[AnyUnpacker unpackNum, AnyUnpacker unpackStr, AnyUnpacker unpackBool]
eqvEquals <<- eqv [arg1, arg2]
return $ Bool $ (primitiveEquals || let (Bool x) = eqvEquals in x)
equal badArgList = throwError $ NumArgs 2 badArgList
</syntaxhighlight>
The first action makes a heterogenous list of 最初のアクションが<code>[unpackNum, unpackStr, unpackBool], and then maps the partially-applied </code>の異型リストを作り、それに部分適用された<code>(unpackEquals arg1 arg2) over it. This gives a list of Bools, so we use the </code>をmapします。これは<code>Bool</code>のリストを作るので、<code>Prelude function </code>の関数[http://www.haskell.org/onlinereport/standard-prelude.html#$vor or] to return true if any single one of them is true.でそのどれか一つでも真であれば真を返すようにします。
二つ目のアクションは<code>eqv?</code>で2つの引数を比べます。<code>equal?</code>の方が<code>eqv?</code>より緩くあってほしいので、<code>equal?</code>は少なくとも<code>eqv?</code>が真を返す時は真を返すべきです。加えて、これによってリストやdotted-listのような場合を扱わなくてよくなります(ただ、これはバグを引き起こします。このセクションの練習問題2番を見てください)。
The second action tests the two arguments with eqv?. Since we want equal? to be looser than eqv?, it should return true whenever eqv? does so. This also lets us avoid handling cases like the list or dotted-list (though this introduces a bug; see exercise #2 in this section).
最後に、<code>equal?</code>はこれらの値の<code>or</code>を取って、結果を<code>Bool</code>コンストラクタに包んで<code>LispVal</code>を返します。<code>let (Bool x) = eqvEquals in x</code>は代数的データ型からさっと値を取り出すやり方で、<code>Bool x</code>を<code>eqvEquals</code>の値にパターンマッチさせ、<code>x</code>を返します。let式の結果はキーワード<code>in</code>に続く式の結果です。
Finally, equal? ors both of these values together and wraps the result in the Bool constructor, returning a LispVal. The <span class="inline_code">let (Bool x) = eqvEquals in x</span> is a quick way of extracting a value from an algebraic type: it pattern matches Bool x against the eqvEquals value, and then returns x. The result of a let-expression is the expression following the keyword "in".
これらの関数を使うには、プリミティブのリストに加える必要があります。
To use these functions, insert them into our primitives list:
<syntaxhighlight lang="haskell">
("car", car),
("cdr", cdr),
("cons", cons),
("eq?", eqv),
("eqv?", eqv),
("equal?", equal)]
</syntaxhighlight>
このコードをコンパイルするには、-fglasgow-extsでGHC拡張を有効にしなければなりません。
To compile this code, you need to enable GHC extensions with -fglasgow-exts:
<syntaxhighlight lang="text">
debian:/home/jdtang/haskell_tutorial/code$% ghc -package parsec -fglasgow-exts -o parser [../code/listing6.4.hs listing6.4.hs]<nowiki>
debian:/home/jdtang/haskell_tutorial/code#% ./simple_parser "(cdr '(a simple test))"
(simple test)
debian:/home/jdtang/haskell_tutorial/code#% ./simple_parser "(car (cdr '(a simple test)))"
simple
debian:/home/jdtang/haskell_tutorial/code#% ./simple_parser "(car '((this is) a test))"
(this is)
debian:/home/jdtang/haskell_tutorial/code#% ./simple_parser "(cons '(this is) 'test)"
((this is) . test)
debian:/home/jdtang/haskell_tutorial/code#% ./simple_parser "(cons '(this is) '())"
((this is))
debian:/home/jdtang/haskell_tutorial/code#% ./simple_parser "(eqv? 1 3)"
#f
debian:/home/jdtang/haskell_tutorial/code#% ./simple_parser "(eqv? 3 3)"
#t
debian:/home/jdtang/haskell_tutorial/code#% ./simple_parser "(eqv? 'atom 'atom)"
#t
</syntaxhighlight>
</nowiki>
練習問題
# <code>#f</code>以外の値全てを真と扱うのではなく、<code>if</code>の定義を変えて条件部に真偽値のみを受け付け、そうでない時はエラーを投げるようにしなさい。
# Instead of treating any non-false value as true, change the definition of "if" so that the predicate accepts only Bool values and throws an error on any others.
# <code>equal?</code>はリストの中の値を<code>equal?</code>ではなく<code>eqv?</code>で比較しているというバグがあります。例えば、<code>(equal? '(1 "2") '(1 2)) => #f</code>となりますが、これは<code>#t</code>を返すことが期待されます。<code>equal?</code>を改良して再帰的にリストの中の値の型を無視するようにしなさい。これを<code>eqv?</code>でやったように明示的に実装してもよいし、リストの節を等価性判定述語を引数に取る別の補助関数に括り出してもよいでしょう。
# equal? has a bug in that a list of values is compared using eqv? instead of equal?. For example, <span class="inline_lisp">(equal? '(1 "2") '(1 2)) = #f</span>, while you'd expect it to be true. Change equal? so that it continues to ignore types as it recurses into list structures. You can either do this explicitly, following the example in eqv?, or factor the list clause into a separate helper function that is parameterized by the equality testing function.
# Implement [http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx_106 cond] and と[http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx_114 case] expressions.を実装しなさい。
# Add the rest of the 残りの[http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.3.5 string functions]. You don't yet know enough to do を実装しなさい。まだ<code>string-set!; this is difficult to implement in </code>の実装方法がわからないと思います。これはHaskell, but you'll have enough information after the next で実装するのが難しいのですが、それについては次の2 sections章でカバーします。
| 