Композиция функций в списке функций!

Question

Мне нужно определить функцию 'Compose', которая принимает список 'L', который является списком функций.Когда я указываю параметр, который будет соответствовать всем функциям в списке, последняя функция оценивает себя, используя этот параметр.Затем результат передается второй последней функции и так далее, пока мы не доберемся до первого элемента (функции) в списке и не получим окончательный результат.

Например

Составить ((fnN -> N + 1) ^ (fn N -> 2 * N) ^ #) 3.

дать ответ 7.

Я должен написать это на функциональном языке программирования, который называетсяSAL (простой аппликативный язык), разработанный лектором в моем колледже (отсюда и забавный синтаксис выше (^ разделяет элементы списка и # отметки в конце списка)).

Если какие-либо решения могут быть написаны в псевдокоде, содержащем вИмейте в виду, я не могу использовать циклы, переменные и т. д., что было бы очень ценно.По-видимому, решение является однострочным ответом.Я предполагаю, что это включает в себя рекурсию (99% наших функций задач выполняют!).

Кроме того, я не понимаю Haskell (думаю, мне придется учиться!), Так что код psuedo или даже простой английский будет отличным вариантом.-

Спасибо большое.

Answer 1

Если решение представляет собой однострочный ответ, это может быть что-то, связанное со сгибом:

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

http://haskell.org/haskellwiki/Compose

Вы также можете реализовать его как правый сгиб, которыйработает так, как вы хотите:

compose = foldr (.) id

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

Answer 2

в Хаскеле:

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

Answer 3

То же самое с использованием моноидов, без очков

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

Или в более общем смысле:

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

Answer 4

Дэн как бы отдает это, но вот подсказка о том, как сделать это самостоятельно. Вы можете записаться по номерам:

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

Вы также можете рекурсировать структуру. Например, список имеет рекурсивную структуру, разбитую на два случая: пустой список и элемент, за которым следует остальная часть списка. Без определенного языка:

List :=   Item x List 
        | Nil

Item отмечает заголовок списка, x - значение, хранящееся в заголовке, а List - хвост. В этой грамматике ваш список будет написан:

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

Правило для списка в синтаксисе, изобретенном вашим профессором, может быть записано рекурсивно как:

List :=   x ^ List
        | #

Функция в списке должна проходить через эту структуру, что означает, что она обрабатывает каждый из двух случаев:

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

Рекурсия, в частности, является термином sum l:List = x + sum xs. Написание этой функции с использованием синтаксиса профессора, оставленного в качестве упражнения.

В вашей задаче ваша метафункция принимает список функций и должна возвращать функцию. Рассмотрим каждый случай, пустой список и элемент (заголовок), за которым следует список (хвост). В последнем случае вы можете рекурсивно использовать свою функцию для получения функции из хвоста, а затем каким-то образом комбинировать ее с головой для возврата функции. Это суть, во всяком случае.

Answer 5

Вот что я использовал:

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