Modèle de récurrence commun

Question

Je m'habitue aux fonctions d'ordre supérieur de Haskell. Habituellement, je peux remplacer les modèles explicites de récursivité par des fonctions telles que map, fold et scan. Cependant, je lance souvent dans le modèle de récurrence suivante que je ne comprends pas comment exprimer en utilisant des fonctions d'ordre supérieur:

f (x:[]) = k x 
    f (x:xs) = g x (f xs) 

Par exemple, supposons que je représente analytique des tableaux. Puis-je créer un type de données telles que:

data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau) 

Si je veux convertir une liste de Expr s dans une structure de tableau, je veux une partie de fonction qui pourrait ressembler à:

f (x:[]) = N x 
    f (x:xs) = S x (f xs) 

Maintenant, Je vois trois options: (1) créer une fonction qui décide, donné un tableau et une liste, si la prochaine branche dans le tableau devrait être S ou N (ou B, mais nous ignorerons ce cas); (2) utiliser une fonction d'ordre supérieur pour encapsuler le modèle de récurrence de f; (3) utiliser une fonction comme f.

Quelle serait la meilleure option?

Answer 1

Je aurait probablement utiliser les éléments suivants:

f xs = foldr g (k (last xs)) (init xs) 

Cela signifie essentiellement que la fin de la liste est remplacé par k x lors du pliage. Grâce à l'évaluation paresseuse présente partout, cela fonctionne même pour des listes infinies.

Il existe deux autres solutions: l'ajout de casse vide et l'utilisation de Maybe.

A) ajouter le cas vide:

Il serait préférable que f [] était bien définie.Ensuite, vous pouvez écrire la définition

f [] = c 
f (x:xs) = g x (f xs) 

qui est f = foldr g c. Par exemple, si vous changez

data Tableau = N Expr | S Expr Tableau | B Expr Tableau Tableau 

à

data Tableau = N | S Expr Tableau | B Expr Tableau Tableau 

alors vous pouvez représenter des tableaux à un seul élément comme S expr N, et la fonction est définie comme une doublure

f = foldr S N 

C'est la meilleure solution tant que le cas vide a du sens.

B) Peut-être utiliser:

D'autre part, si f [] ne peut pas être raisonnablement défini, il est pire. Les fonctions partielles sont souvent considérées comme laides. Pour le rendre total, vous pouvez utiliser Maybe. Définir

f [] = Nothing 
f [x] = Just (k x) 
f (x:xs) = Just (g x w) 
      where Just w = f xs 

C'est une fonction totale - c'est mieux.

Mais maintenant, vous pouvez réécrire la fonction dans:

f [] = Nothing 
f (x:xs) = case f xs of 
       Nothing -> Just (k x) 
       Just w -> Just (g x w) 

qui est un pli droite:

addElement :: Expr -> Maybe Tableaux -> Maybe Tableaux 
addElement x Nothing = Just (N x) 
addElement x (Just w) = Just (S x w) 

f = foldr addElement Nothing 

En général, le pliage est idiomatiques et doit être utilisé lorsque vous vous situez le modèle de récursivité. Sinon, utilisez la récursivité explicite ou essayez de réutiliser les combinateurs existants. S'il y a un nouveau motif, faites un combinateur, mais seulement si vous utiliserez beaucoup le motif - sinon c'est trop. Dans ce cas, le modèle est plié pour les listes non vides définies par: data List a = End a | Cons a (List a).

Answer 2

Si je l'ai bien compris la question, alors voici mon évaluation de vos options:

1. Il est probablement un peu méchant devoir correspondre au tableau de dessous le constructeur (probablement arbitrairement complexe?) afin d'écrire cette fonction. Cette approche semble quelque peu fragile, même si cela fonctionnerait probablement très bien.

2. Je ne vois pas la nécessité de généraliser le motif, étant donné qu'il s'agit d'une fonction récursive fonctionnant sur une structure récursive. L'introduction d'un modèle d'ordre supérieur (je pense) obscurcirait la logique actuelle derrière l'exécution d'une traversée récursive de cette structure de données.

3. Je pense que cela a beaucoup de sens. Comme vous l'avez remarqué, c'est un "pattern" raisonnablement reconnu, mais je pense qu'il correspond bien à la description de l'algorithme pour l'écrire exactement de cette manière. Il peut ne pas être aussi généralisable ou réutilisable, mais étant donné que c'est essentiellement le point crucial de l'approche algorithmique, je pense qu'il est logique d'écrire les cas directement comme vous l'avez fait dans une fonction comme f. Ce serait mon approche préférée.

Désolé de ne pas fournir une réponse particulièrement concrète, mais il est une réponse raisonnable subjective, donc compte tenu des trois options ci-dessus, je choisirais l'option 3 pour des raisons de clarté et de lisibilité.