La composition de fonctions dans une liste de fonctions !

Question

Je dois définir une fonction 'Compose' qui prend une liste 'L' qui est une liste de fonctions. Lorsque je spécifie un paramètre qui conviendra à toutes les fonctions de la liste, la dernière fonction s'évalue elle-même en utilisant ce paramètre. Le résultat est ensuite transmis à l'avant-dernière fonction et ainsi de suite jusqu'à ce que nous arrivions au premier élément (fonction) de la liste et que nous obtenions le résultat final.

Par exemple

Compose ( ( fn N -> N + 1 ) ^ ( fn N -> 2 * N ) ^ # ) 3 .

donnez la réponse 7.

Je dois écrire cela dans un langage de programmation fonctionnel appelé SAL (simple applicative language) conçu par un professeur de mon université (d'où la syntaxe bizarre ci-dessus ( ^ sépare les éléments de la liste et # marque la fin de la liste)).

Si vous pouviez écrire une solution en pseudo-code, en gardant à l'esprit que je ne peux pas utiliser de boucles, de variables, etc. Apparemment, la solution est une réponse en une ligne. J'imagine que cela implique une récursion (99% de nos fonctions de tâches le font !).

De plus, je ne comprends pas Haskell (il va falloir que j'apprenne !), alors un code succinct ou même un anglais simple serait le bienvenu. -

Merci beaucoup.

Answer 1

Si la solution est une réponse d'une ligne, il peut s'agir d'un pli :

compose :: [a -> a] -> a -> a
compose fs v = foldl (flip (.)) id fs $ v

http://haskell.org/haskellwiki/Compose

Vous pouvez également l'implémenter comme un pli droit, qui fonctionne comme vous le souhaitez :

compose = foldr (.) id

*Main> let compose = foldr (.) id
*Main> compose [\x -> x+1, \x -> 2 * x, id] 3
7

Answer 2

En haskell :

compose :: a -> [a -> a] -> a
compose a (x:xs) = x (compose a xs)
compose a [] = a

Answer 3

Dan l'a déjà dit, mais voici une astuce pour le faire vous-même. Vous pouvez récurer sur les nombres :

0! = 1
n! = (n-1)! * n

Vous pouvez également effectuer une récursion sur la structure. Une liste, par exemple, a une structure récursive, décomposée en deux cas : une liste vide, et un élément suivi du reste de la liste. Dans aucun langage particulier :

List :=   Item x List 
        | Nil

Item marque la tête de la liste, x est la valeur stockée dans la tête, et List est la queue. Dans cette grammaire, votre liste serait écrite :

Item ( fn N -> N + 1 ) Item ( fn N -> 2 * N ) Nil

La règle pour une liste dans la syntaxe inventée par votre professeur pourrait s'écrire de manière récursive comme suit :

List :=   x ^ List
        | #

Une fonction sur une liste doit récourir sur cette structure, ce qui signifie qu'elle traite chacun des deux cas :

sum l:List = Nil -> 0
           | Item x xs:List = x + sum xs

La récursion, plus précisément, est le terme sum l:List = x + sum xs . L'écriture de cette fonction en utilisant la syntaxe du professeur est laissée comme un exercice.

Dans votre problème, votre métafonction prend une liste de fonctions et doit retourner une fonction. Considérons chaque cas, la liste vide et un élément (la tête) suivi d'une liste (la queue). Dans ce dernier cas, vous pouvez utiliser récursivement votre fonction pour obtenir une fonction de la queue, puis la combiner d'une manière ou d'une autre avec la tête pour retourner une fonction. C'est l'essentiel, en tout cas.

Answer 4

La même chose en utilisant des monoïdes, sans point

import Data.Monoid
compose :: [a -> a] -> a -> a
compose = appEndo . mconcat . map Endo

Ou de manière plus générale :

import Data.Monoid
compose :: (Functor t, Foldable t) => t (a -> a) -> a -> a
compose = appEndo . foldl1 (<>) . fmap Endo

Answer 5

Voici ce que j'ai utilisé :

compose :: [a -> a] -> a -> a
compose list startingvalue = foldl (\x f -> f x) startingvalue list