Как определить применение Lisp в Haskell?
Разве это определение не должно быть разрешено в ленивом языке, таком как Haskell, в котором функции каррируются?
apply f [] = f
apply f (x:xs) = apply (f x) xs
Это в основном функция, которая применяет данную функцию к заданному списку аргументов, и это очень легко сделать, например, в Лиспе. Есть ли обходные пути?
9 ответов
Трудно дать статический тип 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 может завершиться с ошибкой типа во время выполнения.
По типу рекурсии
Используя полустандарт Text.Printf трюк (придуманный augustss, IIRC), решение может быть закодировано в этом стиле (упражнение). Это может быть не очень полезно, и все же требует некоторой хитрости, чтобы скрыть типы в списке.
Изменить: я не мог придумать способ написать это, без использования динамических типов или списков / экзистенциалов. Хотелось бы увидеть пример
Мне нравится ответ Sjoerd Visscher, но расширения - особенно IncoherentInstances, используемый в этом случае, чтобы сделать частичное применение возможным - может быть немного утомительно. Вот решение, которое не требует никаких расширений.
Сначала мы определяем тип данных функций, которые знают, что делать с любым количеством аргументов. Вы должны прочитать a здесь как "тип аргумента", и b как "тип возвращаемого значения".
data ListF a b = Cons b (ListF a (a -> b))
Затем мы можем написать некоторые (Haskell) функции, которые изменяют эти (variadic) функции. Я использую F суффикс для любых функций, которые находятся в Prelude.
headF :: ListF a b -> b
headF (Cons b _) = b
mapF :: (b -> c) -> ListF a b -> ListF a c
mapF f (Cons v fs) = Cons (f v) (mapF (f.) fs)
partialApply :: ListF a b -> [a] -> ListF a b
partialApply fs [] = fs
partialApply (Cons f fs) (x:xs) = partialApply (mapF ($x) fs) xs
apply :: ListF a b -> [a] -> b
apply f xs = headF (partialApply f xs)
Например, sum функцию можно рассматривать как переменную функцию:
sumF :: Num a => ListF a a
sumF = Cons 0 (mapF (+) sumF)
sumExample = apply sumF [3, 4, 5]
Однако мы также хотим иметь возможность работать с обычными функциями, которые не обязательно знают, что делать с любым количеством аргументов. Так что делать? Ну, как Лисп, мы можем выдать исключение во время выполнения. Ниже мы будем использовать 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, lift1, lift2, lift3и т. д. отдельно, тогда вам нужно включить некоторые расширения. Но вы можете получить довольно далеко без них!
Вот как вы можете обобщить на один lift функция. Сначала мы определим некоторые стандартные числа уровня типа:
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, TypeFamilies, UndecidableInstances #-}
data Z = Z
newtype S n = S n
Затем введите класс типов для подъема. Вы должны прочитать тип I n a b как "n копии a в качестве аргументов, то возвращаемый тип b".
class Lift n a b where
type I n a b :: *
lift :: n -> I n a b -> ListF a b
instance Lift Z a b where
type I Z a b = b
lift _ b = Cons b tooMany
instance (Lift n a (a -> b), I n a (a -> b) ~ (a -> I n a b)) => Lift (S n) a b where
type I (S n) a b = a -> I n a b
lift (S n) f = Cons tooFew (lift n f)
А вот примеры использования f ранее переписать с использованием обобщенного лифта:
fF2 = lift (S (S (S Z))) f
fExample4 = apply fF2 [True, True, True]
fExample5 = apply fF2 [True, False]
fExample6 = apply (partialApply fF2 [True, False]) [False]
Нет, не может. f а также f x разные типы. Из-за статически типизированной природы haskell он не может выполнять никаких функций. Это должно принять определенный тип функции.
предполагать f передается с типом a -> b -> c, затем f x имеет тип b -> c, Но a -> b -> c должен иметь тот же тип, что и a -> b, Следовательно, функция типа a -> (b -> c) должна быть функцией типа a -> b, Так b должен быть таким же, как b -> c, который является бесконечным типом b -> b -> b -> ... -> c, Этого не может быть. (продолжать заменять b -> c за b)
Вот один из способов сделать это в GHC. Здесь и там вам понадобятся аннотации типа, чтобы убедить GHC, что все получится.
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE IncoherentInstances #-}
class Apply f a r | f -> a r where
apply :: f -> [a] -> r
instance Apply f a r => Apply (a -> f) a r where
apply f (a:as) = apply (f a) as
instance Apply r a r 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 на самом деле передаются аргументы, которые 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 (z x) xs
В этом случае рассматриваемая буква "f" определяется с помощью различительного объединения, которое позволяет определить рекурсивный тип данных. Это может быть использовано для решения упомянутой проблемы, я думаю.
С помощью и при помощи некоторых других я определил способ достижения этого (ну, вроде, с помощью пользовательского типа списка), который немного отличается от предыдущих ответов. Это старый вопрос, но, кажется, его все еще посещают, поэтому я добавлю подход для полноты.
Мы используем одно расширение (GADT) с типом списка, немного похожим на тип Даниэля Вагнера, но с типом функции тегирования, а не числом Пеано. Давайте рассмотрим код по частям. Сначала мы устанавливаем расширение и определяем тип списка. Тип данных является полиморфным, поэтому в этой формулировке аргументы не обязательно должны быть одного типа.
{-# LANGUAGE GADTs #-}
-- n represents function type, o represents output type
data LApp n o where
-- no arguments applied (function and output type are the same)
End :: LApp o o
-- intentional similarity to ($)
(:$) :: a -> LApp m o -> LApp (a -> m) o
infixr 5 :$ -- same as :
Давайте определим функцию, которая может взять такой список и применить его к функции. Здесь есть некоторая хитрость типов: функция имеет тип nвызов listApply будет компилироваться, только если этот тип соответствует n тег в нашем списке типов. Оставив наш тип вывода o не указав, мы оставляем некоторую свободу в этом (при создании списка нам не нужно сразу полностью фиксировать тип функции, к которой он может быть применен).
-- the apply function
listApply :: n -> LApp n o -> 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 n o a where
-- Nil :: FList o o a
-- Cons :: a -> FList f o a -> FList (a -> f) o a
Вот 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) (f x)) xs
Это не совсем ответ на ваш первоначальный вопрос, но я думаю, что это может быть ответом на ваш вариант использования.
pure f <*> [arg] <*> [arg2] ...
-- example
λ>pure (\a b c -> (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 (\a b c -> (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 (\a b c -> 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"]
Так что это не та же самая концепция, но это много тех композиционных вариантов использования, и добавляет еще несколько.