Как я могу определить Lisp s в Haskell?

Ответ 1

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

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

Ответ 2

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

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

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

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

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]

Однако мы также хотим иметь дело с нормальными функциями, которые не обязательно знают, что делать с любым количеством аргументов. Так что делать? Ну, например 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, 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]

Ответ 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)

Ответ 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]

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

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

Ответ 8

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

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

Ответ 9

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

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

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