41

この定義は、関数がカレーされるHaskellのような怠惰な言語で許可されるべきではありませんか？

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

これは基本的に、指定された関数を指定された引数のリストに適用する関数であり、たとえばLispで非常に簡単に実行できます。回避策はありますか？

4

8 に答える 8

23

関数に静的型を指定するのは困難です。これはapply、その型が（おそらく異種の）リスト引数の型に依存するためです。Haskellでこの関数を書く方法は少なくとも2つあります。

リフレクションを使用する

アプリケーションの型チェックは実行時まで延期できます。

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を使用せずにこれを書く方法を思い付くことができませんでした。例を見たい

于 2011-05-29T17:12:27.353 に答える
13

私はSjoerdVisscherの返事が好きですが、拡張機能（特に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の拡張機能を有効にする必要があります。しかし、あなたはそれらなしでかなり遠くまで行くことができます！lift2lift3

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]
于 2011-06-09T19:51:03.923 に答える
10

いいえ、できません。fとf xは異なるタイプです。haskellは静的に型付けされているため、機能を果たすことはできません。それは特定のタイプの機能をとらなければなりません。

タイプfがで渡されたとしa -> b -> cます。次にf x、タイプがありb -> cます。ただしa -> b -> c、と同じタイプである必要がありますa -> b。したがって、型の関数は型の関数でa -> (b -> c)なければなりませんa -> b。したがって、無限型であるとb同じである必要があります。存在できません。（の代わりに続けてください）b -> cb -> b -> b -> ... -> cb -> cb

于 2011-05-29T16:30:42.113 に答える
7

これがGHCでそれを行う1つの方法です。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]
于 2011-05-30T10:14:55.273 に答える
4

このコードは、静的型チェックと動的型チェックの違いをよく表しています。apply f静的型チェックを使用すると、コンパイラーは、期待する引数が実際に渡されていることを確認できないfため、プログラムを拒否します。lispでは、チェックは実行時に行われ、プログラムが失敗する可能性があります。

于 2011-05-29T16:28:54.950 に答える
1

これを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」は、再帰データ型の定義を可能にする識別された共用体を使用して定義されます。これは、私が推測する前述の問題を解決するために使用できます。

于 2011-05-30T04:55:28.610 に答える
1

他の人の助けと入力を使って、これを達成する方法を定義しました（まあ、ある種、カスタムリストタイプで）。これは前の回答とは少し異なります。これは古い質問ですが、まだ訪問されているようですので、完全を期すためのアプローチを追加します。

1つの拡張機能（GADT）を使用します。リストの型は、Daniel Wagnerのものと少し似ていますが、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で、適用される関数はすべて同じ型の引数を受け入れる必要があります。

于 2015-09-18T17:23:47.973 に答える
0

これはあなたの最初の質問に対する正確な答えではありませんが、あなたのユースケースに対する答えかもしれないと思います。

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

したがって、これは正確には同じ概念ではありませんが、それらの構成的なユースケースの多くであり、さらにいくつか追加されます。

于 2017-05-05T01:10:52.153 に答える