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

Question

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

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

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

Answer 1

Сложно дать статический тип функции 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), решение можно кодировать в этом стиле (упражнение). Это может быть не очень полезно, и все же требует некоторой хитрости, чтобы скрыть типы в списке.

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

Answer 2

Мне нравится ответ 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]

Answer 3

Нет, не может. 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)

Answer 4

Вот один из способов сделать это в 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]

Answer 5

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

Answer 6

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

Мы используем одно расширение (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 представляет тип аргумента, где применяемая функция также должна принимать аргументы одинакового типа.

Answer 7

Я не уверен, насколько это было бы полезно, так как я пишу это на 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"определяется с помощью различительного объединения, которое позволяет определить рекурсивный тип данных.Думаю, это можно использовать для решения упомянутой проблемы.

Answer 8

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

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"]

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