14

私は Haskell を学んでおり、演習として、コードに続く read_from 関数を Haskell に変換しようとしています。Peter Norvig の Scheme インタプリタから引用。これを行う簡単な方法はありますか？

def read(s):
    "Read a Scheme expression from a string."
    return read_from(tokenize(s))

parse = read

def tokenize(s):
    "Convert a string into a list of tokens."
    return s.replace('(',' ( ').replace(')',' ) ').split()

def read_from(tokens):
    "Read an expression from a sequence of tokens."
    if len(tokens) == 0:
        raise SyntaxError('unexpected EOF while reading')
    token = tokens.pop(0)
    if '(' == token:
        L = []
        while tokens[0] != ')':
            L.append(read_from(tokens))
        tokens.pop(0) # pop off ')'
        return L
    elif ')' == token:
        raise SyntaxError('unexpected )')
    else:
        return atom(token)

def atom(token):
    "Numbers become numbers; every other token is a symbol."
    try: return int(token)
    except ValueError:
        try: return float(token)
        except ValueError:
            return Symbol(token)
4

2 に答える 2

54

Python を Haskell に「音訳」する簡単な方法があります。これは、モナド変換子を巧みに使用することで実現できますが、これは恐ろしく聞こえるかもしれませんが、実際にはそうではありません。Haskell では、変更可能な状態 (たとえば、appendandpop操作が変更を実行している) や例外などの効果を使用する場合、純粋性のために、もう少し明示的にする必要があります。上から始めましょう。

parse :: String -> SchemeExpr
parse s = readFrom (tokenize s)

Python docstring には「文字列からスキーム式を読み取る」と書かれていたので、これを自由に型シグネチャ ( String -> SchemeExpr) としてエンコードしました。型が同じ情報を伝えるため、その docstring は時代遅れになります。さて... とは何ですかSchemeExpr? コードによると、スキーム式は、int、float、symbol、またはスキーム式のリストにすることができます。これらのオプションを表すデータ型を作成しましょう。

data SchemeExpr
  = SInt    Int
  | SFloat  Float
  | SSymbol String
  | SList   [SchemeExpr]
  deriving (Eq, Show)

Int扱っている を として扱う必要があることをHaskell に伝えるにはSchemeExpr、 でタグ付けする必要がありSIntます。他の可能性についても同様です。に移りましょうtokenize。

tokenize :: String -> [Token]

再び、docstring は型シグネチャに変わります: aを s のStringリストに変えTokenます。さて、トークンとは何ですか？コードを見ると、左右の括弧文字が明らかに特別なトークンであり、特定の動作を示していることがわかります。それ以外は... 特別ではありません。括弧を他のトークンとより明確に区別するためにデータ型を作成することもできますが、元の Python コードにもう少し近づけるために、文字列を使用してみましょう。

type Token = String

では、書いてみましょうtokenize。最初に、関数チェーンを Python に少し似たものにする簡単な小さな演算子を書きましょう。Haskell では、独自の演算子を定義できます。

(|>) :: a -> (a -> b) -> b
x |> f = f x

tokenize s = s |> replace "(" " ( "
               |> replace ")" " ) "
               |> words

wordsのHaskell版ですsplit。ただし、Haskell にはreplace、私が知っている調理済みのバージョンはありません。トリックを行う必要があるものは次のとおりです。

-- add imports to top of file
import Data.List.Split (splitOn)
import Data.List (intercalate)

replace :: String -> String -> String -> String
replace old new s = s |> splitOn old
                      |> intercalate new

splitOnとのドキュメントを読めばintercalate、この単純なアルゴリズムは完全に理にかなっているはずです。Haskellers は通常、これを と書きますが、 Python の読者が理解しやすいようにここでreplace old new = intercalate new . splitOn old使用しました。|>

replaceは 3 つの引数を取ることに注意してください。Haskell では、任意の関数を部分的に適用できます。これは非常に優れています。|>型の安全性が高いことを除けば、UNIX パイプのように機能します。

まだ私と一緒に？にスキップしましょうatom。ネストされたロジックは少し見にくいので、少し異なる方法でクリーンアップしてみましょう。このタイプを使用してEither、より優れたプレゼンテーションを行います。

atom :: Token -> SchemeExpr
atom s = Left s |> tryReadInto SInt
                |> tryReadInto SFloat
                |> orElse (SSymbol s)

Haskell には自動強制変換関数intandfloatがないため、代わりに をビルドしtryReadIntoます。仕組みは次のとおりですEither。値をスレッド化します。Either値は aまたはLeftaRightです。従来、Leftエラーまたは失敗を通知するために使用され、Right成功または完了を通知します。Haskell では、Python 風の関数呼び出しチェーンをシミュレートするには、「self」引数を最後の引数として配置するだけです。

tryReadInto :: Read a => (a -> b) -> Either String b -> Either String b
tryReadInto f (Right x) = Right x
tryReadInto f (Left s) = case readMay s of
  Just x -> Right (f x)
  Nothing -> Left s

orElse :: a -> Either err a -> a
orElse a (Left _) = a
orElse _ (Right a) = a

tryReadInto文字列を解析しようとしている型を決定するために、型推論に依存しています。解析が失敗した場合、そのLeft位置に同じ文字列を再生成するだけです。成功した場合は、必要な機能を実行し、結果をそのRight位置に配置します。前の計算が失敗した場合に備えて、値をorElse指定することで を排除できます。ここで例外の代わりとしてEitherどのように機能するかがわかりますか? Python コード内の s はEither常に関数自体の内部でキャッチされるため、決して例外が発生しないことがわかっています。同様に、Haskell コードでは、関数の内部で使用していますが、公開するインターフェイスは純粋です。ValueExceptionatomEitherToken -> SchemeExpr、目に見える副作用はありません。

では、に移りましょうread_from。まず、自問自答してください: この関数にはどのような副作用がありますか? tokensを介して引数を変更しpop、 という名前のリストに内部変更を加えていLます。また、SyntaxError例外が発生します。この時点で、ほとんどの Haskeller は「ああ、いや、副作用だ!ひどい!」と言って手を上げます。しかし、実際のところ、Haskeller は常に副作用も使用します。人々を怖がらせて成功を避けるために、私たちはそれらを「モナド」と呼んでいます。変異はモナドで実現できState、例外はモナドで実現できますEither(驚き!)。両方を同時に使用したいので、実際には「モナド変換子」を使用しますが、これについては後で説明します。そうじゃないクラフトを過ぎて見ることを学ぶと、怖いです。

まず、いくつかのユーティリティ。これらは単純な配管操作です。raisePython のように「例外を発生」させ、PythonwhileMのように while ループを記述させます。後者の場合、効果が発生する順序を明示する必要があります。最初に効果を実行して条件を計算し、それが の場合Trueは本体の効果を実行し、再度ループします。

import Control.Monad.Trans.State
import Control.Monad.Trans.Class (lift)

raise = lift . Left

whileM :: Monad m => m Bool -> m () -> m ()
whileM mb m = do
  b <- mb
  if b
  then m >> whileM mb m
  else return ()

ここでも、純粋なインターフェースを公開したいと考えています。ただし、 a が存在する可能性があるSyntaxErrorため、型シグネチャで結果がaまたは a のいずれかになることを示します。これは、Java でメソッドが発生させる例外に注釈を付ける方法を連想させます。SyntaxError が発生する可能性があるため、の型シグネチャも変更する必要があることに注意してください。SchemeExprSyntaxErrorparse

data SyntaxError = SyntaxError String
                 deriving (Show)

parse :: String -> Either SyntaxError SchemeExpr

readFrom :: [Token] -> Either SyntaxError SchemeExpr
readFrom = evalStateT readFrom'

渡されたトークン リストに対してステートフルな計算を実行します。ただし、Python とは異なり、呼び出し元に失礼なことをしたり、渡されたリスト自体を変更したりすることはありません。代わりに、独自の状態空間を確立し、与えられたトークン リストに初期化します。構文糖衣を提供する記法を使用doして、命令的にプログラミングしているように見せます。StateTモナド変換子は、get、put、およびmodify状態操作を提供します。

readFrom' :: StateT [Token] (Either SyntaxError) SchemeExpr
readFrom' = do
  tokens <- get
  case tokens of
    [] -> raise (SyntaxError "unexpected EOF while reading")
    (token:tokens') -> do
      put tokens' -- here we overwrite the state with the "rest" of the tokens
      case token of
        "(" -> (SList . reverse) `fmap` execStateT readWithList []
        ")" -> raise (SyntaxError "unexpected close paren")
        _   -> return (atom token)

readWithList型シグネチャを見てもらいたいので、この部分を別のコードの塊に分割しました。コードのこの部分は新しい scopeStateTを導入するので、以前のモナド スタックの上に別のスコープを単純に重ねます。ここで、、、getおよびput操作modifyはL、Python コードで呼び出されるものを参照します。でこれらの操作を実行したい場合は、モナド スタックの 1 つのレイヤーを取り除くためにtokens、操作の前に を付けるだけです。lift

readWithList :: StateT [SchemeExpr] (StateT [Token] (Either SyntaxError)) ()
readWithList = do
  whileM ((\toks -> toks !! 0 /= ")") `fmap` lift get) $ do
    innerExpr <- lift readFrom'
    modify (innerExpr:)
  lift $ modify (drop 1) -- this seems to be missing from the Python

Haskell では、リストの最後に追加するのは効率が悪いので、代わりに先頭に追加し、後でリストを逆にしました。パフォーマンスに関心がある場合は、より優れたリストのようなデータ構造を使用できます。

完全なファイルは次のとおりです: http://hpaste.org/77852

したがって、Haskell を初めて使用する場合、これはおそらく恐ろしく見えるでしょう。私のアドバイスは、少し時間を与えることです。モナドの抽象化は、人々が思っているほど恐ろしいものではありません。ほとんどの言語に組み込まれているもの (ミューテーション、例外など) は、代わりに Haskell がライブラリを介して提供することを学ぶ必要があります。Haskell では、必要な効果を明示的に指定する必要があり、それらの効果を制御することは少し不便です。しかしその代わりに、Haskell はより多くの安全性を提供するため、間違った効果を誤って混同することはありません。また、効果を組み合わせてリファクタリングする方法を完全に制御できるため、より強力になります。

于 2012-11-17T17:27:14.330 に答える
12

Haskell では、操作対象のデータを変更するアルゴリズムは使用しません。いいえ、それを行う簡単な方法はありません。ただし、変数の更新を避けるために、再帰を使用してコードを書き直すことができます。以下のソリューションでは、MissingHパッケージを使用してreplaceいます。

import Data.String.Utils (replace)
import Data.Tree  
import System.Environment (getArgs)

data Atom = Sym String | NInt Int | NDouble Double | Para deriving (Eq, Show)

type ParserStack = (Tree Atom, Tree Atom)

tokenize = words . replace "(" " ( " . replace ")" " ) " 

atom :: String -> Atom
atom tok =
  case reads tok :: [(Int, String)] of
    [(int, _)] -> NInt int
    _ -> case reads tok :: [(Double, String)] of
      [(dbl, _)] -> NDouble dbl
      _ -> Sym tok

empty = Node $ Sym "dummy"
para = Node Para

parseToken (Node _ stack, Node _ out) "(" =
  (empty $ stack ++ [empty out], empty [])
parseToken (Node _ stack, Node _ out) ")" =
  (empty $ init stack, empty $ (subForest (last stack)) ++ [para out])
parseToken (stack, Node _ out) tok =
  (stack, empty $ out ++ [Node (atom tok) []])

main = do
  (file:_) <- getArgs
  contents <- readFile file
  let tokens = tokenize contents
      parseStack = foldl parseToken (empty [], empty []) tokens
      schemeTree = head $ subForest $ snd parseStack
  putStrLn $ drawTree $ fmap show schemeTree

foldlhaskeller の基本的な構造化再帰ツールであり、 while ループや への再帰呼び出しと同じ目的を果たしますread_from。コードは大幅に改善できると思いますが、Haskell にはあまり慣れていません。以下は、上記を Python にほぼそのまま音訳したものです。

from pprint import pprint
from sys import argv

def atom(tok):
    try:
        return 'int', int(tok)
    except ValueError:
        try:
            return 'float', float(tok)
        except ValueError:
            return 'sym', tok

def tokenize(s):
    return s.replace('(',' ( ').replace(')',' ) ').split()

def handle_tok((stack, out), tok):
    if tok == '(':
        return stack + [out], []
    if tok == ')':
        return stack[:-1], stack[-1] + [out] 
    return stack, out + [atom(tok)]

if __name__ == '__main__':
    tokens = tokenize(open(argv[1]).read())
    tree = reduce(handle_tok, tokens, ([], []))[1][0]
    pprint(tree)
于 2012-11-18T02:33:50.227 に答える