Обозначение для рекурсивного вызова пользовательского типа

Возможный дубликат:
Перебор строки и замена отдельных символов подстроками в haskell

Я пытаюсь реализовать функцию, которая просматривает строку ([символы]) и проверяет каждую букву, следует ли заменить эту букву другой строкой. Например, у нас может быть [Chars], состоящий из «XYF» и правил, которые говорят «X = HYHY», «Y = OO», тогда наш вывод должен стать «HYHYOOF».

Я хочу использовать следующие два типа, которые я определил:

type Letters = [Char]
data Rule = Rule Char Letters deriving Show

Моя идея состоит в том, что функция должна выглядеть примерно так, как показано ниже, с использованием охранников. Однако проблема в том, что я не могу найти никакой информации о том, как должен выглядеть рекурсивный вызов, когда я хочу просмотреть все свои правила, чтобы увидеть, подходит ли какое-либо из них к текущей букве x. Я надеюсь, что кто-нибудь может дать несколько советов о том, как идет запись.

apply :: Letters -> [Rule] -> Letters
apply _ _ = []
apply (x:xs) (Rule t r:rs)  
| x /= t = apply x (Rule t rs)
| x == t = r++rs:x
| otherwise  =

types recursion haskell notation
person John    schedule 19.10.2012    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Я бы предложил вспомогательную функцию, чтобы проверить, соответствует ли правило,

matches :: Char -> Rule -> Bool
matches c (Rule x _) = c == x

а затем вы проверяете для каждого символа, есть ли какие-либо соответствующие правила

apply :: Letters -> [Rule] -> Letters
apply [] _ = []
apply s [] = s
apply (c:cs) rules = case filter (matches c) rules of
                       [] -> c : apply cs rules
                       (Rule _ rs : _) -> rs ++ apply cs rules

Если вы попробуете явную рекурсию для rules внутри apply, это станет слишком уродливым, так как вам нужно запомнить полный список правил для замены более поздних символов.

person Daniel Fischer    schedule 19.10.2012
comment
я думал, что вспомогательная функция не нужна, так как вы можете просто проверить, равен ли x значению t (в моем примере), но я вижу, куда идет ваш метод. спасибо за вклад. - person John; 19.10.2012
comment
Проблема в том, что у вас есть два списка для обхода, список букв и правила. Делать это в той же функции нехорошо, так как вам нужно восстановить полный набор правил для следующей буквы, вам потребуются три аргумента. Разделение двух обходов дает более короткий, простой для понимания и поддержки код. - person Daniel Fischer; 19.10.2012

arrow_upward
2
arrow_downward

Я бы посоветовал вам научиться делать это с помощью общих служебных функций. Две ключевые функции, которые вам нужны здесь:

  1. lookup :: Eq a => a -> [(a, b)] -> Maybe b. Находит сопоставление в списке ассоциаций — списке пар, используемых для представления карты или словаря.
  2. concatMap :: (a -> [b]) -> [a] -> [b]. Это похоже на map, но функция, сопоставленная со списком, возвращает список, а результаты объединяются (concatMap = concat . map).

Чтобы использовать lookup, вам нужно изменить тип Rule на этот более общий синоним:

type Rule = (Char, String)

Помните также, что String является синонимом [Char]. Это означает, что concatMap при применении к String заменяет каждый символ строкой. Теперь ваш пример можно записать так (я изменил порядок аргументов):

apply :: [Rule] -> String -> String
apply rules = concatMap (applyChar rules) 

-- | Apply the first matching rule to the character.
applyChar :: [Rule] -> Char -> String
applyChar rules c = case lookup c rules of
                      Nothing -> [c]
                      Just str -> str

-- EXAMPLE
rules = [ ('X', "HYHY")
        , ('Y', "OO") ]

example = apply rules "XYF"  -- evaluates to "HYHYOOF"

Я изменил порядок аргументов apply, потому что, когда аргумент имеет тот же тип, что и результат, часто помогает сделать этот аргумент последним (упрощает цепочку функций).

Мы можем пойти дальше и превратить это в однострочник, используя вспомогательную функцию fromMaybe :: a -> Maybe a -> a из модуля Data.Maybe (fromMaybe default Nothing = default, fromMaybe default (Just x) = x):

import Data.Maybe

apply rules = concatMap (\c -> fromMaybe [c] $ lookup c rules)

Упражнение, которое вы можете сделать, чтобы дополнить это, состоит в том, чтобы вручную написать свою версию всех этих служебных функций: lookup, concatMap (разбить на concat :: [[a]] -> [a] и map :: (a -> b) -> [a] -> [b]) и fromMaybe. Таким образом, вы сможете понять «полный стек», задействованный в этом решении.

person Luis Casillas    schedule 19.10.2012

arrow_upward
1
arrow_downward

Мое решение структурно похоже на другие, но использует монады:

import Control.Monad 
import Data.Functor 
import Data.Maybe 

match :: Char -> Rule -> Maybe Letters
match c (Rule c' cs) = cs <$ guard (c == c')

apply :: Letters -> [Rule] -> Letters
apply cs rules = 
  [s | c <- cs
     , s <- fromMaybe [c] $ msum $ map (match c) rules]

Первая монада, с которой мы имеем дело, это Maybe a. На самом деле это немного больше, MonadPlus, что позволяет нам использовать msum (что сводит что-то вроде [Nothing, Just 2, Nothing, Just 3] к первому «попаданию», здесь Just 2).

Вторая монада — [a], что позволяет нам использовать понимание списка в apply.

person Landei    schedule 19.10.2012