La composition des fonctions dans une liste de fonctions!

Question

J'ai besoin de 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 passé à la deuxième dernière fonction et ainsi de suite jusqu'à ce que nous obtenions le premier élément (fonction) dans la liste et nous obtenons le résultat final.

E.g.

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

donner la réponse 7.

Je dois écrire ceci dans un langage de programmation fonctionnelle appelée SAL (simple, langage applicatif) conçu par un professeur dans mon collège (syntaxe donc drôle ci-dessus (^ seperates éléments de liste et des marques # fin de la liste)).

Si des solutions pouvaient être écrites en pseudo-code, je ne pourrais pas utiliser de boucles, de variables, etc., ce qui serait très apprécié. Apparemment, la solution est une réponse d'une ligne. J'imagine que cela implique une récursivité (99% des fonctions de notre tâche font!).

Aussi je ne comprends pas Haskell (devinez que je vais devoir apprendre!) Donc le code de psuedo ou même l'anglais simple serait grand. -

Merci beaucoup.

Answer 1

à haskell:

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

Answer 2

Dan lui donne genre de loin, mais voici un indice sur la façon de le faire vous-même. Vous pouvez parcourir plusieurs chiffres:

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

Vous pouvez également faire une répétition 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 aucune langue particulière:

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 sera écrit:

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

La règle pour une liste dans la syntaxe de votre professeur a inventé pourrait être écrit récursive comme:

List := x^List 
     | # 

Une fonction sur une liste doit récursivité sur cette la structure, ce qui signifie qu'il gère chacun des deux cas:

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

la récursivité, en particulier, est le terme sum l:List = x + sum xs. Ecrire cette fonction en utilisant la syntaxe du professeur reste un exercice.

Dans votre problème, votre métafonction prend une liste de fonctions et doit retourner une fonction. Considérez 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 3

Si la solution est une réponse d'une ligne, il pourrait être quelque chose qui implique un pli:

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

http://haskell.org/haskellwiki/Compose

Vous pouvez également mettre en œuvre 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 4

Voici ce que je:

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

Answer 5

Les mêmes en utilisant monoids, Pointfree

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

Ou un peu plus généralement:

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