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。这可以通过巧妙地使用 monad 转换器来完成，这听起来很吓人，但事实并非如此。您会看到，由于纯粹性，在 Haskell 中，当您想要使用可变状态（例如，appendandpop操作正在执行突变）或异常等效果时，您必须使其更加明确。让我们从顶部开始。

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

Python 文档字符串说“从字符串中读取 Scheme 表达式”，所以我只是冒昧地将其编码为类型签名 ( String -> SchemeExpr)。该文档字符串已过时，因为该类型传达了相同的信息。现在......什么是a SchemeExpr？根据您的代码，方案表达式可以是 int、float、符号或方案表达式列表。让我们创建一个表示这些选项的数据类型。

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

为了告诉 HaskellInt我们正在处理的应该被视为一个SchemeExpr，我们需要用 标记它SInt。其他可能性也是如此。让我们继续tokenize。

tokenize :: String -> [Token]

同样，文档字符串变成了类型签名：将 aString变成Tokens 的列表。那么，什么是令牌？如果您查看代码，您会注意到左右括号字符显然是特殊标记，表示特定行为。其他任何东西都是……​​不特别的。虽然我们可以创建一种数据类型来更清楚地将括号与其他标记区分开来，但让我们只使用字符串，以更接近原始 Python 代码。

type Token = String

现在让我们尝试写作tokenize。首先，让我们快速编写一个小操作符，让函数链看起来更像 Python。在 Haskell 中，您可以定义自己的运算符。

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

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

words是 Haskell 的版本split。replace然而，Haskell 没有我所知道的预煮版本。这是一个可以解决问题的方法：

-- 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

如果您阅读 and 的文档splitOn，intercalate这个简单的算法应该很有意义。Haskellers 通常将其写为replace old new = intercalate new . splitOn old，但我|>在这里使用它是为了让 Python 观众更容易理解。

请注意，它replace需要三个参数，但上面我只用两个参数调用它。在 Haskell 中，您可以部分应用任何函数，这非常简洁。|>工作起来有点像 unix 管道，如果你不知道的话，除了类型安全性更高。

还在我这儿？让我们跳到atom。嵌套逻辑有点难看，所以让我们尝试一种稍微不同的方法来清理它。我们将使用该Either类型进行更好的演示。

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

Haskell 没有自动强制转换函数intand float，因此我们将构建tryReadInto. 它是这样工作的：我们将Either围绕值进行线程化。Either值是 a或Lefta Right。通常，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，以防之前的计算失败。你能看到这里是如何Either替代异常的吗？由于ValueExceptionPython 代码中的 s总是被函数本身捕获，我们知道它atom永远不会引发异常。同样，在 Haskell 代码中，即使我们Either在函数内部使用，我们暴露的接口也是纯的：Token -> SchemeExpr，没有外在可见的副作用。

好的，让我们继续read_from。首先，问自己一个问题：这个功能有什么副作用？tokens它通过改变它的参数pop，并且它在名为 的列表上有内部突变L。它也引发了SyntaxError异常。在这一点上，大多数Haskellers会举手说“哦，不！副作用！恶心！” 但事实是，Haskellers 也一直在使用副作用。我们只是称它们为“单子”，以吓跑人们并不惜一切代价避免成功。突变可以用Statemonad 来完成，例外情况可以用 monad 来完成Either（惊喜！）。我们希望同时使用两者，所以我们实际上会使用“monad 转换器”，我会稍微解释一下。不是这样可怕，一旦你学会了看过去。

首先，一些实用程序。这些只是一些简单的管道操作。raise将让我们像在 Python 中一样“引发异常”，并whileM让我们像在 Python 中一样编写一个 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，因此我们将在类型签名中指出结果将是aSchemeExpr或 a SyntaxError。这让人想起在 Java 中如何注释方法将引发的异常。请注意，类型签名parse也必须更改，因为它可能会引发 SyntaxError。

data SyntaxError = SyntaxError String
                 deriving (Show)

parse :: String -> Either SyntaxError SchemeExpr

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

我们将对传入的令牌列表执行有状态计算。然而，与 Python 不同的是，我们不会对调用者粗鲁并改变传递给我们的列表。相反，我们将建立自己的状态空间并将其初始化为给定的令牌列表。我们将使用do符号，它提供语法糖，使它看起来像我们在命令式编程。StateTmonad 转换器为我们提供了、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部分分解为单独的代码块，因为我希望您查看类型签名。这部分代码引入了一个新的作用域，因此我们只需StateT在我们之前拥有的 monad 堆栈之上再分层一个。现在，get、put和modify操作指的L是 Python 代码中调用的东西。如果我们想在 上执行这些操作tokens，那么我们可以简单地在操作前加上lift，以便剥离一层 monad 堆栈。

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 的新手，那么这可能看起来很可怕。我的建议是给它一些时间。Monad 抽象并不像人们想象的那么可怕。您只需要了解大多数语言所包含的内容（突变、异常等），Haskell 反而通过库提供。在 Haskell 中，您必须明确指定您想要的效果，并且控制这些效果不太方便。然而，作为交换，Haskell 提供了更多的安全性，因此您不会意外地混淆错误的效果，并且功能更强大，因为您可以完全控制如何组合和重构效果。

于 2012-11-17T17:27:14.330 回答
12

在 Haskell 中，您不会使用一种算法来改变它所操作的数据。所以不，没有直接的方法可以做到这一点。但是，可以使用递归重写代码以避免更新变量。下面的解决方案使用MissingH包，因为 Haskell 烦人地没有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

foldl是 haskeller 的基本结构化递归工具，它与您的 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 回答