¡La composición de las funciones en una lista de funciones!

Question

Necesito definir una función 'Componer' que tome una lista 'L' que es una lista de funciones. Cuando especifico un parámetro que se adaptará a todas las funciones en la lista, la última función se evalúa utilizando este parámetro. El resultado se pasa a la segunda función y así sucesivamente hasta que lleguemos al primer elemento (función) en la lista y obtenemos el resultado final.

E.g.

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

dar la respuesta 7.

tengo que escribir esto en un lenguaje funcional de programación llamado SAL (lenguaje aplicativo sencilla) ideado por el profesor de mi universidad (sintaxis, por tanto, divertida anterior (^ seperates elementos de la lista y las marcas # final de la lista)).

Si se pueden escribir soluciones en pseudocódigo teniendo en cuenta que no puedo usar bucles, variables, etc. que serían muy apreciadas. Aparentemente la solución es una respuesta de una línea. Me imagino que implica la recursión (¡el 99% de nuestras funciones lo hacen!).

Además, no entiendo a Haskell (¡supongo que tendré que aprender!) Así que el código de psuedo o incluso el inglés sencillo sería genial. -

Muchas gracias.

Answer 1

en Haskell:

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

Answer 2

Dan tipo de lo delata, pero aquí va una pista sobre cómo hacerlo usted mismo. Puede recurse sobre números:

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

También puede recurse sobre la estructura. Una lista, por ejemplo, tiene una estructura recursiva, dividida en dos casos: una lista vacía y un elemento seguido por el resto de la lista. En ningún idioma en particular:

List := Item x List 
     | Nil 

Item marca el principio de la lista, x es el valor almacenado en la cabeza, y List es la cola. En esta gramática, su lista se escribiría:

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

La regla para una lista en la sintaxis de su profesor inventó podría escribirse de forma recursiva como:

List := x^List 
     | # 

Una función en una lista debe recursivo sobre este estructura, lo que significa que se encarga de cada uno de los dos casos:

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

la recursión, específicamente, es el término sum l:List = x + sum xs. Escribir esta función usando la sintaxis del profesor dejada como ejercicio.

En su problema, su metafunción toma una lista de funciones y debe devolver una función. Considere cada caso, la lista vacía y un elemento (la cabeza) seguido de una lista (la cola). En el último caso, puede usar recursivamente su función para obtener una función de la cola, y luego combinarla de alguna manera con la cabeza para devolver una función. Esa es la esencia, en cualquier caso.

Answer 3

Si la solución es una respuesta de una línea, podría ser algo relacionado con un pliegue:

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

http://haskell.org/haskellwiki/Compose

También puede implementar como un pliegue derecha, que funciona de la forma que desee :

compose = foldr (.) id 

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

Answer 4

Esto es lo que he usado:

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

Answer 5

Los mismos utilizando monoides, pointfree

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

O algo más general:

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