如何将这个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)

Answer 1

有一种直接的方法可以将Python"音译"到Haskell中.这可以通过聪明地使用monad变换器来实现,这听起来很可怕,但事实并非如此.你可以看到,由于纯度的原因,当你想要使用诸如可变状态(例如append,pop操作正在执行变异)或异常之类的效果时,你必须使其更加明确.让我们从顶部开始吧.

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

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

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

为了告诉Haskell Int我们正在处理的应该被视为a SchemeExpr,我们需要用它来标记它SInt.与其他可能性一样.让我们继续吧tokenize.

tokenize :: String -> [Token]

同样,docstring变成了一个类型签名:将a String转换为Tokens 列表.好吧,什么是令牌？如果你查看代码,你会注意到左边和右边的paren字符显然是特殊的标记,它表示特定的行为.还有别的......非特别的.虽然我们可以创建一种数据类型来更清楚地区分parens和其他令牌,但我们只需使用Strings,就可以更接近原始的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通常会将其写为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)

哈斯克尔不具备自动魔法coersion功能int和float,所以不是我们将建立tryReadInto.以下是它的工作原理:我们将Either围绕价值观.的Either值可以是一个Left或一个Right.通常,Left用于发信号错误或故障,同时Right信号成功或完成.在Haskell中,要模拟Python-esque函数调用链接,只需将"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也一直使用副作用.我们只称它们为"monad",以便吓跑人们并不惜一切代价避免成功.可以使用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 ()

我们再次希望公开一个纯粹的接口.然而,有机会的话,将有一个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部分分解为单独的代码块,因为我希望您看到类型签名.这部分代码引入了一个新的范围,因此我们只需将另一个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提供了更多的安全性,因此您不会意外地混淆错误的效果和更多的功能,因为您可以完全控制如何组合和重构效果.

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