Как перевести этот питон на Haskell?

Я изучаю Haskell и как упражнение, которое я пытаюсь преобразовать, записывает функцию read_from, следующую за кодом в Haskell. Взято с переводчика Петра Норвига. Есть ли простой способ сделать это?

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)

Ответ 1

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

Ответ 2

Существует простой способ "транслитерировать" Python в Haskell. Это можно сделать с помощью умного использования монадных трансформаторов, что звучит страшно, но на самом деле это не так. Вы видите, из-за чистоты, в Haskell, когда вы хотите использовать такие эффекты, как изменчивое состояние (например, операции append и pop выполняют мутацию) или исключения, вы должны сделать это немного более явным. Пусть начнется вверху.

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

В docstring Python сказано "Чтение выражения схемы из строки", поэтому я просто взял на себя обязательство кодировать это как подпись типа (String -> SchemeExpr). Эта docstring становится устаревшей, потому что тип передает ту же информацию. Теперь... что такое SchemeExpr? В соответствии с вашим кодом выражение схемы может быть символом int, float, symbol или list. Позвольте создать тип данных, который представляет эти параметры.

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

Чтобы сообщить Haskell, что мы имеем дело с Int, следует рассматривать как SchemeExpr, мы должны пометить его SInt. Аналогично другим возможностям. Перейдите к tokenize.

tokenize :: String -> [Token]

Опять же, docstring превращается в сигнатуру типа: превратите a String в список Token s. Ну, что за токен? Если вы посмотрите на код, вы заметите, что символы левого и правого символов являются, по-видимому, особыми токенами, которые сигнализируют о конкретном поведении. Все остальное... неспешно. Хотя мы могли бы создать тип данных, чтобы более четко различать 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 pipe, если вы не могли сказать, кроме как с большей безопасностью типа.

Еще со мной? Переходим к 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-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 выступает в качестве замены для исключений здесь? Поскольку ValueException в коде Python всегда попадает внутри самой функции, мы знаем, что atom никогда не будет создавать исключение. Аналогично, в коде Haskell, хотя мы использовали Either внутри функции, интерфейс, который мы выставляем, является чистым: Token -> SchemeExpr, не имеет видимых внешних эффектов.

ОК, перейдите к read_from. Во-первых, задайте себе вопрос: какие побочные эффекты имеет эта функция? Он мутирует свой аргумент tokens через pop, и он имеет внутреннюю мутацию в списке с именем L. Он также вызывает исключение SyntaxError. На данный момент, большинство Haskellers будут поднимать руки, говоря "oh noe! Побочные эффекты! Грубые!" Но правда в том, что Haskellers все время используют побочные эффекты. Мы просто называем их "монадами", чтобы отпугнуть людей и избежать успеха любой ценой. Мутацию можно выполнить с помощью монады State и исключений с монадой Either (сюрприз!). Мы будем хотеть использовать оба одновременно, поэтому на самом деле будем использовать "монадные трансформаторы", которые я объясню немного. Это не так страшно, как только вы научитесь видеть прошлое.

Во-первых, несколько утилит. Это всего лишь несколько простых работ по сантехнике. raise позволит нам "вызывать исключения", как в Python, а whileM позволит нам написать цикл while, как в Python. Для последнего мы просто должны четко указать, в каком порядке должны происходить эффекты: сначала выполните эффект для вычисления условия, а затем, если он 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 поверх стека монады которые мы имели раньше. Теперь операции get, put и modify на предмет, называемый L в коде Python. Если мы хотим выполнить эти операции на 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 обеспечивает большую безопасность, поэтому вы случайно не смешиваете неправильные эффекты и больше энергии, потому что вы полностью контролируете, как комбинировать и рефакторировать эффекты.