如何将这个 Python 代码翻译成 Haskell？

Question

我正在学习 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)

- Yofe

---

如果你想进一步学习这个项目，可以看看《48小时内写一个Scheme解释器》（http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/Parsing）。 - AndrewC

+1 我一直在寻找一个好的借口来写关于这个的博客。我想我会把它写成一个SO答案。 - Dan Burton

正如AndrewC所建议的那样，我认为使用解析器组合在Haskell中完成这个任务更自然。我强烈推荐阅读那篇教程。Monad transformer非常棒，但在Haskell中完成这个任务并不必要。 - Zach Conn

Answer 1

有一种直接的方法可以将Python“音译”成Haskell。这可以通过巧妙地使用单子变换器来实现，听起来很可怕，但其实并不是。你知道，在Haskell中，由于纯度（purity）的原因，当你想要使用像可变状态（例如append和pop操作正在执行的突变）或异常等效果时，你必须使它更加明确。让我们从顶部开始。

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

Python的文档字符串说“从字符串中读取Scheme表达式”，所以我就擅自将其编码为类型签名（String -> SchemeExpr）。该文档字符串变得过时，因为类型传递了相同的信息。那么，什么是SchemeExpr？根据您的代码，Scheme表达式可以是int、float、符号或Scheme表达式列表。让我们创建一个表示这些选项的数据类型。

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

为了告诉 Haskell 我们正在处理的 Int 应该被视为一个 SchemeExpr，我们需要用 SInt 给它打上标签。其他情况也是如此。现在让我们继续进行 tokenize。

tokenize :: String -> [Token]

再次强调，文档字符串将变为类型签名：将String转换为Token列表。那么，什么是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的文档，这个简单的算法应该很清晰。Haskeller通常会将其写成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没有像int和float这样的自动转换函数，因此我们将构建一个tryReadInto函数。下面是它的工作原理：我们将在Either值之间传递。 Either值可以是Left或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 如何在此处充当异常的替代品吗？由于 Python 代码中的 ValueException 总是在函数内部被捕获，因此我们知道 atom 永远不会引发异常。同样，在 Haskell 代码中，即使我们在函数内部使用了 Either，我们公开的接口也是纯的：Token -> SchemeExpr，没有外部可见的副作用。

现在，让我们移动到 read_from。首先，问自己一个问题：这个函数有哪些副作用？它通过 pop 改变其参数 tokens，并对名为 L 的列表进行内部修改。它还引发了 SyntaxError 异常。此时，大多数 Haskeller 都会举起双手说“哦不！副作用！恶心！”但事实是，Haskeller 也经常使用副作用。我们只是称它们为“单子”以吓唬人们，并避免一切代价获得成功。使用 State 单子可以完成变异，使用 Either 单子（惊喜！）可以处理异常。我们将同时使用两者，因此实际上将使用“单子转换器”，稍后我会解释。一旦学会看过杂乱无章的部分，这并不可怕。

首先是一些工具函数。这些只是一些简单的管道操作。如 Python 中所示，raise 允许我们“抛出异常”，而 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 ()

我们希望再次暴露出一个纯接口。不过，有可能会出现 SyntaxError，因此我们将在类型签名中指示结果将是要么SchemeExpr 要么 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 符号表示，它提供了语法糖，使它看起来像我们在编写命令式代码。 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部分拆分为一个单独的代码块，因为我希望您看到类型签名。这部分代码引入了一个新作用域， 因此我们只需在之前的monad堆栈上再添加一个StateT。现在，get、put和modify操作 都引用了Python代码中称为L的对象。如果我们想对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提供了更多的安全性，以防止您意外混淆错误的效果，并且提供了更多的功能，因为您完全可以控制如何组合和重构效果。

- Dan Burton

---

如果你要混合使用Either和State单子，那基本上就是Parser单子的一种变体：newtype Parser a = Parser { runParser :: String -> Either ErrorMessage (String, a) }，它与StateT String (Either ErrorMessage) a完全等价。此外，它恰好适用于他正在做的事情：解析。如果你只为它定义一个单子实例，那么你就不需要引入单子转换器了。 - Gabriella Gonzalez

或者，您可以使用 newtype Parser a = Parser { runParser :: StateT String (Either ErrorMessage) a } deriving (Monad) 并免费获得所有机制。 - Gabriella Gonzalez

我想要强调的是，Haskell提供了常见的命令式语言特性作为库。需要改变状态吗？使用State。需要异常处理吗？使用Either。需要控制反转吗？使用Cont。新手应该学会如何识别和使用适当的工具，因此最好分别说明每个工具的用法。 - Dan Burton

这是一段非常出色的代码，但对于初学者如何在 Haskell 中实现这个功能的建议却很糟糕。 :D - Heinrich Apfelmus

@HeinrichApfelmus 确实，我的目标不是让代码在 Haskell 中更加惯用。相反，我希望尽可能地让它在 Haskell 中更具有 Python 风格。 - Dan Burton

自从十一月中旬发布问题以来，我一直在学习Haskell。最近我又看了你的答案，现在能够欣赏它了。所以我想说感谢你花时间给出如此详细和有见地的回答。 - Yofe

Answer 2

在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是Haskell程序员的基本结构化递归工具，它和你的while循环和对read_from的递归调用有着相同的作用。我认为代码可以改进很多，但我不太熟悉Haskell。下面是将上述内容几乎直接转换成Python的结果：

foldl是Haskell程序员的基本结构化递归工具，它的作用类似于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)

- Björn Lindqvist