notation pour un appel récursif sur le type défini par l'utilisateur

Question

Possible en double:
Iterating through a String and replacing single chars with substrings in haskell

Je suis en train de mettre en œuvre une fonction qui ressemble à une chaîne ([Chars]) et les chèques pour chaque lettre si cette lettre doit être remplacée par une autre chaîne. Par exemple, nous pourrions avoir un [Chars] composé de "XYF" et des règles qui disent "X = HYHY", "Y = OO", alors notre sortie devrait devenir "HYHYOOF".

Je veux utiliser les deux types que je définis ci-après:

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

Mon idée est que la fonction devrait ressembler à quelque chose comme ce qui suit ci-dessous à l'aide des gardes. Le problème est cependant que je ne peux trouver aucune information sur la façon dont l'appel récursif devrait ressembler quand je veux parcourir toutes mes règles pour voir si l'un d'entre eux correspond à la lettre x actuelle. J'espère que n'importe qui peut donner quelques conseils sur comment la notation va.

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 = 

Answer 1

Je suggère une fonction d'assistance pour vérifier si une règle correspond,

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

et vous vérifiez chaque caractère s'il existe des règles de correspondance

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 

Si vous essayez une récursion explicite sur rules au sein de apply, il deviendra trop moche, car vous devez vous rappeler la liste complète des règles pour remplacer les caractères plus tard.

Answer 2

Je vous suggère d'apprendre à le faire avec des fonctions utilitaires génériques. Deux fonctions clés que vous voulez ici:

1. lookup :: Eq a => a -> [(a, b)] -> Maybe b. Trouve un mappage dans une liste d'associations: une liste de paires utilisées pour représenter une carte ou un dictionnaire.
2. concatMap :: (a -> [b]) -> [a] -> [b]. Ceci est similaire à map, mais la fonction mappée sur la liste renvoie une liste et les résultats sont concaténés (concatMap = concat . map).

Pour utiliser lookup vous devez changer votre type Rule à ce synonyme plus générique:

type Rule = (Char, String) 

Rappelez-vous aussi que String est synonyme de [Char]. Cela signifie que concatMap, lorsqu'il est appliqué à String, remplace chaque caractère par une chaîne. Maintenant, votre exemple peut être écrit de cette façon (je l'ai changé les ordres d'argument):

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" 

j'ai changé l'ordre des arguments de apply parce que quand un argument a le même type que le résultat, il est souvent utile de faire cet argument le dernier (facilite le chaînage des fonctions).

Nous pouvons aller plus loin et transformer cela en une seule ligne en utilisant la fonction d'utilité fromMaybe :: a -> Maybe a -> a à partir du module Data.Maybe (fromMaybe default Nothing = default, fromMaybe default (Just x) = x):

import Data.Maybe 

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

Un exercice que vous pouvez faire pour compléter C'est pour écrire votre version de toutes ces fonctions d'utilité sur votre propre: lookup, concatMap (décomposer en concat :: [[a]] -> [a] et map :: (a -> b) -> [a] -> [b]), et fromMaybe. De cette façon, vous pouvez comprendre la «pile complète» impliquée dans cette solution.

Answer 3

Ma solution est structurellement similaire aux autres, mais utilise monades:

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]  

La première monade que nous avons affaire à Maybe a. Il est en fait un peu plus, un MonadPlus, ce qui nous permet d'utiliser msum (qui résume quelque chose comme [Nothing, Just 2, Nothing, Just 3] au premier "hit", ici Just 2).

La deuxième monade est [a], ce qui nous permet d'utiliser une compréhension de liste dans apply.