10

まだここでHaskell初心者。私は自分が間違った仮定でトラブルに巻き込まれるのに十分知っています。次の機能がある場合...

quadsum w x y z = w+x+y+z

リストを取得し、のような指定された関数のパラメーターとして各要素を使用しquadsum、後で使用するためにカリー化された関数を返すことができる関数が必要です。

私は何かをしようとしてきました...

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

これができることを期待して...

magicalFunctionMaker (quadsum) [4,3,2]

次のようなカリー化関数を取得しています...:

(((quadsum 4) 3) 2)

または、代わりに、次のように呼び出します。

magicalFunctionMaker (quadsum) [4,3,2,1]

その結果...

((((quadsum 4) 3) 2) 1)

これは可能ですか?私はどのくらい見当違いですか?

4

6 に答える 6

7

Haskell型システムを誤解していると思います。

まず第一に、あなたの「quadsum」関数はすでにカレーされています。「quadsum43」と記述して、2と1を追加の引数として期待する関数を取り戻すことができます。「((((quadsum 4)3)2)1)」に相当する「quadsum 4 321」と書くと。

Haskellでは、整数のリストは「(4,3,2,1)」のように整数またはタプルとは異なるタイプを持っています。これを考えると、あなたが何をしようとしているのかを理解するのはかなり難しいです。これを書くとどうなるでしょうか?

magicalFunctionMaker quadsum [5,4,3,2,1]

「magicalFunctionMaker」は「foldl」に似ていますが、foldlに指定する関数が2つの引数しかとらない点が異なります。だからあなたは書くことができます:

mySum = foldl (+) 0

これは、リストを取得して要素を合計する関数を返します。

(ところで、これを理解したら、foldlとfoldrの違いについて学びます。

編集:

あなたの質問を読み直して、私はあなたが得ようとしていると思います:

magicalFunctionMaker quadSum [4,3,2,1] :: Integer
magicalFunctionMaker quadSum [4,3,2] :: Integer -> Integer

magicalFunctionMakerのタイプはリスト引数の長さに依存するため、これは不可能です。これは、動的型付けを意味します。誰かが言ったように、多変量関数はこれに近づく何かをすることができます(ただし、リスト引数はありません)が、それにはかなりの数のミリオレグタイプのハッカーが必要です。

于 2010-09-23T07:38:00.033 に答える
4

ポールジョンソンの答えはほとんどそれをカバーしています。ただやる

quadsum 4 3 2

結果は、タイプがの必要な関数になりますInteger -> Integer

しかし、これでは不十分な場合もあります。数値のリストを取得したり、リストの長さがわからなかったり、関数に要素を適用したりする必要がある場合があります。これは少し難しいです。あなたはできません:

magicalFunction2 f [] = f
magicalFunction2 f (x1:x2:xs) = f x1 x2

結果にはさまざまなタイプがあるためです。最初のケースでは、結果に2つの引数が必要であり、2番目のケースでは、完全に適用された関数であるため、これ以上の引数は許可されません。この場合、最善の方法は、十分な引数が使用可能になるまでリストと元の関数を保持することです。

type PAPFunc f a result = Either (f, [a]) result

magicfunc f xs = Left (f,xs)

apply (Left (f,xs)) ys = Left (f,xs++ys)
apply p _              = p

simp2 :: PAPFunc (a->a->b) a b -> PAPFunc (a->a->b) a b
simp2 (Left (f,(x1:x2:xs))) = Right (f x1 x2)
simp2 p = p

今、あなたはできる:

Main> let j = magicfunc (+) []
Main> let m = apply j [1]
Main> let n = apply m [2,3]

Main> either (const "unfinished") show $ simp2 m
"unfinished"
Main> either (const "unfinished") show $ simp2 n
"3"

アリティごとに個別の簡略化関数が必要になります。これは、TemplateHaskellで最も簡単に修正できる問題です。

Haskellでは(リストの引数ではなく)引数のリストを使用するのは非常に厄介な傾向があります。これは、複数の結果がすべて異なるタイプであり、異なるタイプの引数の可変数を持つコレクションのサポートがほとんどないためです。ソリューションの3つの一般的なカテゴリを見てきました。

  1. ケースごとに個別に明示的にコーディングします(すぐに多くの作業になります)。

  2. テンプレートHaskell。

  3. システムハッカリーと入力します。

私の答えは主に、1の痛みを和らげようとすることを扱っています。2と3は気弱な人向けではありません。

編集:この問題に関連するHackageのパッケージがいくつかあることがわかりました。 「iteratee」の使用:

import qualified Data.Iteratee as It
import Control.Applicative

magic4 f = f <$> It.head <*> It.head <*> It.head <*> It.head

liftedQuadsum = magic4 quadsum
-- liftedQuadsum is an iteratee, which is essentially an accumulating function
-- for a list of data

Main> p <- It.enumChunk (It.Chunk [1]) liftedQuadsum
Main> It.run p
*** Exception: EofException
Main> q <- It.enumChunk (It.Chunk [2,3,4]) p
Main> It.run q
10

しかし、「iteratee」と「enumerator」はおそらくやり過ぎです。

于 2010-09-23T13:13:12.763 に答える
3

私はこれと同じ問題に直面しました:私は次のような機能を持っています

someFunc :: Int -> Int -> Int -> Int

私がやりたいのは、例えば次のような魔法の機能を作ることです

listApply :: [Int] -> (Int -> Int -> Int -> Int) -> Int

私が言うことができるように

listApply [1,2,3] someFunc

本能的に、これを行うために何らかの型システムの魔法を行うことが可能であるはずであるように思われ、ジョンの答えは同意します。明示的なローリングとアンローリングの束を使用して明示的に等再帰的なデータ型を作成することを含む同様の問題に対する解決策があります(たとえば、型とプログラミング言語の第20章、またはこのスレッドの4番目の投稿を参照してください)。

私はしばらくの間、タイプソリューションをハッキングしました。それは可能だと感じますが、Template Haskellを試してみる前に、私はそれを完全に機能させることができませんでした。

{-# LANGUAGE TemplateHaskell #-}    

import Language.Haskell.TH
import Language.Haskell.TH.Syntax

lApply :: [Int] -> String -> ExpQ
lApply    []  fn = return $ VarE (mkName fn)
lApply (l:ls) fn = [| $(lApply ls fn) l |]

(LANGUAGEプラグマまたは-XTemplateHaskellコマンドラインスイッチを使用することを忘れないでください。)

これを使用するには、次のようにスプライス内でlApplyを呼び出します。

> $(lApply [1,2] "+")
3

呼び出したい関数の名前を含む文字列を使用する必要があることに注意してください。関数をExpQに直接リフトすることはできませんが、そのグローバルバインディングを参照することはできます。これがどのように迷惑になるかがわかります。また、リストをトラバースする方法のため、引数はリスト内で逆の順序で提示する必要があります。

他にもいくつかの問題があります。これを他のデータ型に一般化するには、これらの型に対応するインスタンスがLiftクラスに含まれている必要があります。たとえば、Doubleにはインスタンスがありませんが、簡単に作成できます。

instance Lift Double where
        lift x = return $ LitE (RationalL (toRational x))

Litデータ型にはDoubleLコンストラクターがありませんが、Fractionalクラスの一般メンバーにスプライスされるため、RationalLを代わりに使用できます。

引数として型の混合をとる関数でこれを使用したい場合、リストは混合型にすることができないため、リストを渡すことはできません。タプルを使用してこれを行うことができますが、これは正直なところ、TemplateHaskellを使用するのはそれほど難しくありません。その場合、内部に適切なタイプのタプルを取り、それを必要な関数呼び出しにマップする関数のASTを生成する関数を作成します。あるいは、適切に作成されたADT内に引数タイプをラップすることもできます。これは、ちなみにTemplateHaskellを使用して作成することもできます。これは読者の練習問題として残されています:)

最後に、標準のTemplateHaskellの制限がすべて適用されます。たとえば、GHCステージの制限により、この関数が定義されているモジュールからこの関数を呼び出すことはできません。

テンプレートHaskellは面白くて面白いものですが、完全に正直に言うと、等再帰データ型ソリューションはおそらく少しパフォーマンスが高く、明らかにTHを追加で使用する必要はありません。私が戻ってきて、それが機能するようになった場合はフォローアップを投稿します:)

于 2010-11-22T01:37:04.120 に答える
2

異なる長さのケースを「手動で」リストすることさえできません。

mf f [] = f
mf f [x] = f x
mf f [x,y] = f x y

--Occurs check: cannot construct the infinite type: t = t1 -> t
--Probable cause: `f' is applied to too many arguments
--In the expression: f x
--In the definition of `mf': mf f [x] = f x

つまり、mfは任意の「アリティ」の機能をとることができないので、1つを決める必要があります。同じ理由で、任意のリストをタプルに変換することはできません。タプルが保持する要素の数を言うことはできませんが、型システムは知る必要があります。

「forall」を使用してfを再帰型a=a-> aに制限することで解決策があるかもしれません(http://www2.tcs.ifi.lmu.de/~abel/fomega/hm.htmlを参照)。ただし、動作させることができず(Leksahにフラグ-XRankNTypesをどこかで使用するように指示する必要があるようです)、fの制限により、関数がかなり役に立たなくなります。

[編集]

考えてみると、あなたが望むものに最も近いものは、おそらくある種のreduce関数です。Paulが指摘したように、これはfoldl、foldr ...に似ています(ただし、以下のバージョンには「余分な引数」がなく、foldlと比較して同種の型があります。空のリストの基本ケースが欠落していることに注意してください)

mf :: (a → a → a) -> [a] -> a
mf f [x] = x
mf f (x:y:xs) = mf f ((f x y) : xs)
于 2010-09-23T08:00:24.083 に答える
1

私は他の投稿を編集するつもりでしたが、これはそれ自体で十分な大きさです。

これは「タイプマジック」でそれを行う1つの方法ですが、特定の数の引数の関数に固有のリフティング関数が必要なため、やや最適ではないように感じます(以下で詳しく説明します)。

再帰データ型を定義することから始めましょう

data RecT a = RecR a
            | RecC (a -> RecT a)

したがって、タイプRecTの変数は、ラップされた結果(RecR)にすることも、継続的な再帰(RecC)にすることもできます。

では、どのようにして何かを取得し、それをタイプRecT aにキャストしますか?

値は簡単です:

valRecT x = RecR x

RecRxは明らかにタイプRecTaです。

idのように1つの引数を取る関数はどうですか?

idRecT x = RecC $ \x -> RecR x

RecCは、変数を受け取り、タイプRecTaを返す関数をラップします。表現

\x -> RecR x

以前に観察したように、RecRxはタイプRecTaであるため、これはまさにそのような関数です。

より一般的には、任意の1つの引数関数を解除できます。

lift1RecT :: (a -> a) -> RecT a
lift1RecT fn = RecC $ \a -> RecR $ fn a

これを一般化するには、RecC内でより深くネストされた関数呼び出しを繰り返しラップします。

lift2RecT :: (a -> a -> a) -> RecT a
lift2RecT fn = RecC $ \b -> RecC $ \a -> RecR $ fn b a

lift3RecT :: (a -> a -> a -> a) -> RecT a
lift3RecT fn = RecC $ \c -> RecC $ \b -> RecC $ \a -> RecR $ fn c b a

さて、これですべての作業を行って、任意の数の引数の関数を単一の型RecTaに変換しました。これをどのように使用しますか?

関数適用の1つのレベルを簡単に書き留めることができます。

reduceRecT :: RecT a -> a -> RecT a
reduceRecT (RecC fn) = fn
reduceRecT  _        = undefined

つまり、reduceRecTは、タイプRecT aとタイプaの引数を取り、1レベル削減された新しいRecTaを返します。

RecT内で終了した計算を結果に展開することもできます。

unrollRecT :: RecT a -> a
unrollRecT (RecR fn) = fn
unrollRecT  _        = undefined

これで、引数のリストを関数に適用する準備が整いました。

lApply :: [a] -> RecT a -> a
lApply    []  fn = unrollRecT fn
lApply (l:ls) fn = lApply ls $ (reduceRecT fn) l

最初に基本ケースを考えてみましょう。計算が終了したら、結果をアンラップして返します。再帰的な場合は、引数リストを1つ減らしてから、リストの先頭を減らしたfnに適用してfnを変換し、新しいRecTaを作成します。

これを試してみましょう:

lApply [2,5] $ lift2RecT (**)
> 32.0

では、このアプローチの長所と短所は?ええと、テンプレートHaskellバージョンは部分的なリストアプリケーションを行うことができます。これは、ここに示されている等再帰型のソリューションには当てはまりません(ただし、原則として、これをいくつかの醜い方法で修正できます)。タイプソリューションには、より多くのボイラープレートコードが関連付けられているという欠点もあります。使用するすべてのNに対してlistNRecTが必要です。最後に、混合変数型の関数にlApplyを適用する場合、これを類似のタプルソリューションに一般化するのははるかに簡単ではありません。

もちろん、もう1つの興味深い可能性は、TemplateHaskellを使用してlistNRecT関数を生成することで簡潔さを高めることです。これにより、定型文がなくなりますが、ある意味では、両方の実装の欠点があります。

于 2010-11-22T03:17:13.080 に答える
1

働かないと思います。たとえば、のタイプが。のタイプとは(((quadsum 4) 3) 2)異なります。Intger -> Integer((((quadsum 4) 3) 2) 1)Integer

于 2010-09-23T05:31:37.937 に答える