Как определить применение Lisp в Haskell?

Разве это определение не должно допускаться на ленивом языке, таком как Haskell, в котором функционируют функции?

apply f [] = f apply f (x:xs) = apply (fx) xs 

Это в основном функция, которая применяет данную функцию к указанному списку аргументов и очень легко выполняется в Lisp, например. Есть ли обходные пути?

Трудно дать статический тип функции apply , так как ее тип зависит от типа (возможно, гетерогенного) аргумента списка. Есть как минимум два способа написать эту функцию в Haskell, о которой я могу думать:

Использование отражения

Мы можем отложить проверку типов приложения до времени выполнения:

 import Data.Dynamic import Data.Typeable apply :: Dynamic -> [Dynamic] -> Dynamic apply f [] = f apply f (x:xs) = apply (f `dynApp` x) xs 

Обратите внимание, что теперь программа Haskell может выйти из строя с ошибкой типа во время выполнения.

Через рекурсию classа типа

Используя Text.Printf трюк Text.Printf (изобретенный августом, IIRC), решение может быть закодировано в этом стиле (упражнении). Это может быть не очень полезно, хотя и требует некоторого трюка, чтобы скрыть типы в списке.

Редактировать: я не мог придумать способ написать это, не используя динамические типы или hlists / existentials. Хотелось бы увидеть пример

Мне нравится ответ Sjoerd Visscher, но расширения, особенно IncoherentInstances , используемые в этом случае для частичного применения, могут быть немного сложными. Вот решение, которое не требует каких-либо расширений.

Во-первых, мы определяем тип данных функций, которые знают, что делать с любым количеством аргументов. Вы должны читать здесь как «тип аргумента», а b как «тип возврата».

 data ListF ab = Cons b (ListF a (a -> b)) 

Затем мы можем написать некоторые (Haskell) функции, которые выполняют эти (вариативные) функции. Я использую суффикс F для любых функций, которые находятся в Prelude.

 headF :: ListF ab -> b headF (Cons b _) = b mapF :: (b -> c) -> ListF ab -> ListF ac mapF f (Cons v fs) = Cons (fv) (mapF (f.) fs) partialApply :: ListF ab -> [a] -> ListF ab partialApply fs [] = fs partialApply (Cons f fs) (x:xs) = partialApply (mapF ($x) fs) xs apply :: ListF ab -> [a] -> b apply f xs = headF (partialApply f xs) 

Например, функцию sum можно рассматривать как вариационную функцию:

 sumF :: Num a => ListF aa sumF = Cons 0 (mapF (+) sumF) sumExample = apply sumF [3, 4, 5] 

Однако мы также хотим иметь дело с нормальными функциями, которые не обязательно знают, что делать с любым количеством аргументов. Так что делать? Ну, как и Lisp, мы можем исключить исключение во время выполнения. Ниже мы будем использовать f как простой пример невариантной функции.

 f True True True = 32 f True True False = 67 f _ _ _ = 9 tooMany = error "too many arguments" tooFew = error "too few arguments" lift0 v = Cons v tooMany lift1 f = Cons tooFew (lift0 f) lift2 f = Cons tooFew (lift1 f) lift3 f = Cons tooFew (lift2 f) fF1 = lift3 f fExample1 = apply fF1 [True, True, True] fExample2 = apply fF1 [True, False] fExample3 = apply (partialApply fF1 [True, False]) [False] 

Конечно, если вам не нравится шаблон для определения lift0 , lift2 , lift3 , lift3 и т. Д. Отдельно, тогда вам нужно включить некоторые расширения. Но вы можете получить довольно далеко без них!

Вот как вы можете обобщить одну функцию lift . Во-первых, мы определяем некоторые стандартные номера уровня типа:

 {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, TypeFamilies, UndecidableInstances #-} data Z = Z newtype S n = S n 

Затем введите class для подъема. Вы должны прочитать тип n I nab как « n копий аргумента a а затем тип возврата b ».

 class Lift nab where type I nab :: * lift :: n -> I nab -> ListF ab instance Lift Z ab where type IZ ab = b lift _ b = Cons b tooMany instance (Lift na (a -> b), I na (a -> b) ~ (a -> I nab)) => Lift (S n) ab where type I (S n) ab = a -> I nab lift (S n) f = Cons tooFew (lift nf) 

И вот примеры, использующие f , были переписаны с использованием обобщенного лифта:

 fF2 = lift (S (S (SZ))) f fExample4 = apply fF2 [True, True, True] fExample5 = apply fF2 [True, False] fExample6 = apply (partialApply fF2 [True, False]) [False] 

Нет, не может. f и fx – разные типы. Из-за статически типизированного характера haskell он не может выполнять какую-либо функцию. Он должен принимать определенный тип функции.

Пусть f передается с типом a -> b -> c . Тогда fx имеет тип b -> c . Но a -> b -> c должен иметь тот же тип, что a -> b . Следовательно, функция типа a -> (b -> c) должна быть функцией типа a -> b . Таким образом, b должно быть таким же, как b -> c , что является бесконечным типом b -> b -> b -> ... -> c . Он не может существовать. (продолжать заменять b -> c на b )

Вот один из способов сделать это в GHC. Вам понадобятся annotations некоторых типов здесь и там, чтобы убедить GHC, что все это сработает.

 {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE IncoherentInstances #-} class Apply far | f -> ar where apply :: f -> [a] -> r instance Apply far => Apply (a -> f) ar where apply f (a:as) = apply (fa) as instance Apply rar where apply r _ = r test = apply ((+) :: Int -> Int -> Int) [1::Int,2] apply' :: (a -> a -> a) -> [a] -> a apply' = apply test' = apply' (+) [1,2] 

Этот код является хорошей иллюстрацией различий между статической и динамической проверкой типов. При статической проверке типов компилятор не может быть уверен, что apply f действительно передается аргументам, которые ожидаются, поэтому он отклоняет программу. В lisp проверка выполняется во время выполнения, и тогда программа может выйти из строя.

Я не уверен, насколько это было бы полезно, поскольку я пишу это в F #, но я думаю, что это можно легко сделать и в Haskell:

 type 'a RecFunction = RecFunction of ('a -> 'a RecFunction) let rec apply (f: 'a RecFunction) (lst: 'a list) = match (lst,f) with | ([],_) -> f | ((x::xs), RecFunction z) -> apply (zx) xs 

В этом случае рассматриваемый «f» определяется с помощью дискриминированного объединения, которое позволяет определять тип рекурсивного типа данных. Это может быть использовано для решения упомянутой проблемы, я думаю.

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

Мы используем одно расширение (GADT), с типом списка, немного похожим на Daniel Wagner, но с типом функции тегов, а не с числом Peano. Давайте рассмотрим код в деталях. Сначала мы устанавливаем расширение и определяем тип списка. Тип данных является полиморфным, поэтому в этой формулировке аргументы не должны иметь один и тот же тип.

 {-# LANGUAGE GADTs #-} -- n represents function type, o represents output type data LApp no where -- no arguments applied (function and output type are the same) End :: LApp oo -- intentional similarity to ($) (:$) :: a -> LApp mo -> LApp (a -> m) o infixr 5 :$ -- same as : 

Давайте определим функцию, которая может взять такой список и применить его к функции. Здесь есть некоторые трюки типа: функция имеет тип n , вызов listApply будет компилироваться, только если этот тип соответствует тегу n в нашем типе списка. Если оставить наш тип вывода o неопределенным, мы оставляем в нем некоторую свободу (при создании списка нам не нужно сразу полностью фиксировать ту функцию, к которой она может быть применена).

 -- the apply function listApply :: n -> LApp no -> o listApply fun End = fun listApply fun (p :$ l) = listApply (fun p) l 

Это оно! Теперь мы можем применить функции к аргументам, хранящимся в нашем типе списка. Ожидается больше? 🙂

 -- showing off the power of AppL main = do print . listApply reverse $ "yrruC .B lleksaH" :$ End print . listApply (*) $ 1/2 :$ pi :$ End print . listApply ($) $ head :$ [1..] :$ End print $ listApply True End 

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

 -- Can't do this :( -- listApply (**) $ foldr (:$) End [2, 32] 

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

 -- Alternative definition -- data FList noa where -- Nil :: FList ooa -- Cons :: a -> FList foa -> FList (a -> f) oa 

Здесь a представляет тип аргумента, в котором применимая функция также должна принимать аргументы одного и того же типа.

Я не уверен в использовании этой функции. Списки являются неизменяемыми и применяются для возврата функции. Это заставляет меня думать, что ваш вариант использования будет иметь более прямое решение. Однако я могу предложить следующий способ:

 instance Show (a -> b) where show a = "function" apply :: Num a => (a -> a) -> [a] -> (a -> a) apply f [] = f apply f (x:xs) = apply ((\_ -> f) (fx)) xs 

Это не совсем ответ на ваш первоначальный вопрос, но я думаю, что это может быть ответ на ваш случай использования.

 pure f <*> [arg] <*> [arg2] ... -- example λ>pure (\abc -> (a*b)+c) <*> [2,4] <*> [3] <*> [1] [7,13] λ>pure (+) <*> [1] <*> [2] [3] 

Прикладной экземпляр списка намного шире, чем этот супер узкий вариант использования, хотя …

 λ>pure (+1) <*> [1..10] [2,3,4,5,6,7,8,9,10,11] -- Or, apply (+1) to items 1 through 10 and collect the results in a list λ>pure (+) <*> [1..5] <*> [1..5] [2,3,4,5,6,3,4,5,6,7,4,5,6,7,8,5,6,7,8,9,6,7,8,9,10] {- The applicative instance of list gives you every possible combination of elements from the lists provided, so that is every possible sum of pairs between one and five -} λ>pure (\abc -> (a*b)+c) <*> [2,4] <*> [4,3] <*> [1] [9,7,17,13] {- that's - 2*4+1, 2*3+1, 4*4+1, 4*3+1 Or, I am repeating argC when I call this function twice, but a and b are different -} λ>pure (\abc -> show (a*b) ++ c) <*> [1,2] <*> [3,4] <*> [" look mah, other types"] ["3 look mah, other types","4 look mah, other types","6 look mah, other types","8 look mah, other types"] 

Так что это совсем не то же понятие, но это много тех композиционных прецедентов, и добавляет еще несколько.

  • почему byte + = 1 компилировать, но byte = byte + 1 нет?
  • Как найти числовые столбцы в Pandas?
  • Типы и classы переменных
  • Каков тип строкового литерала в C ++?
  • Что такое тип данных uintptr_t
  • Условный оператор не может действовать неявно?
  • «Неполный тип» в classе, который имеет один и тот же тип самого classа
  • Каковы различия между типами () и isinstance ()?
  • В чем разница между 'int?' и 'int' в C #?
  • Тип аргумента для сигнала и слота Qt, имеет ли значение задание отступников?
  • Как запросить json-столбец для пустых объектов?
  • Давайте будем гением компьютера.