5

タイプの関数qが必要です：

q :: ([b] -> b) -> ([(a, b)] -> (a, b))

リストから単一の要素を選択する関数を取り、その関数をリストのペアから単一のペアを選択するコンテキストに持ち上げます* (ペアの最初の要素を完全に無視します)。

そのような関数を書くことさえ可能ですか? 私はこれについて進歩を遂げることができませんでした。

*「リフト」は正しい言葉ですか?

使用例: 関数がある場合:

safeMaximum :: b -> [b] -> b

> safeMaximum 18 [] 
18
> safeMaximum 18 [4,5,1,4,3]
5

次にsafeMaximum、ペアのリストから、2 番目の要素が最大のペアを取得するために使用します。

liftedSafeMaximum :: (a, b) -> [(a, b)] -> (a, b)
liftedSafeMaximum val = q val safeMaximum

liftedSafeMaximum ("?", 3) []
> ("?", 3)
liftedSafeMaximum ("?", 3) [("xyz", 1), ("123", 3), ("hi", 2)]
> ("123", 3)
4

5 に答える 5

4

セレクター関数の定義を少し改良したい場合は、このようなものを機能させることができます。リストから要素を直接選択する代わりに、関心のある各要素の部分を見ることを可能にする射影が与えられた場合に、リストから項目を選択する多形関数を用意します。

qあとは、snd使用する投影としてそれを指定するだけです。

{-# LANGUAGE Rank2Types #-}

import Data.Ord (comparing)
import Data.List (maximumBy)

q :: (forall c. (c -> b) -> c -> [c] -> c) -> (a, b) -> [(a, b)] -> (a, b)
q select = select snd

safeMaximumOn :: Ord b => (a -> b) -> a -> [a] -> a
safeMaximumOn proj x xs = maximumBy (comparing proj) (x:xs)

liftedSafeMaximum :: Ord b => (a, b) -> [(a, b)] -> (a, b)
liftedSafeMaximum = q safeMaximumOn

これは、私の以前の回答と本質的に同じ考えです。

于 2012-10-05T15:38:34.663 に答える
3

あなたはこれを「関数をコンテキストに持ち上げる」ことを望んでいると説明しているので、それが何を意味するのか見てみましょう。目的のタイプから始めます。

q :: (a, b) -> ([b] -> b) -> ([(a, b)] -> (a, b))

...目的のコンテキストを楽観的に抽象化できます。

q :: f b -> ([b] -> b) -> ([f b] -> f b)

fそれが であると仮定すると(Functor動機付けの例ではそうです)、 に持ち上げることができ[b] -> bますf [b] -> f b。[f b] -> f [b]によく似たtype の関数があれば、そこから目的の型に到達できますsequence。

代わりにfisの場合を考えてみましょう: functionと listが与えられた場合、 type の引数をリスト内のすべての関数に適用し、セレクター関数を使用して、 type の結果を返す関数を返すことができます。それはあなたが求めているもののように聞こえます！((->) a)[b] -> b[a -> b]a -> bab

残念ながら、特定の例では機能しません。Monad関連するのはライターモナドであり、Monoid制約を追加し、リスト内aのすべての値のモノイド和を常に返しaます。

失敗する理由は、値の不透明な選択関数しかないためbです。これは、コンテキストなしで使用する必要がありsequence、個々のコンテキストをすべて抽出する (そしてプロセスでマージする) ようなものを使用する必要があります。必要な関数を作成するには、コンテキストを各要素に関連付ける情報を失うことなく、コンテキストをマージする方法が必要です。

リーダーモナドは、関連する「マージ」プロセスが一意であるため、他のモナドが機能しない場所で機能します。単一の引数を複数の関数に適用することは、 and によって与えられる正規コモノイドの反変使用に基づいて\x -> ()おり\x -> (x, x)、各結果要素が元の入力を一意に決定します。 .

共変位置で同じプロパティを取得するには、各入力要素が結果の合計を一意に決定するモノイドが必要です。これは、すべての入力が同じでなければならないことを意味し、値が 1 つだけの型でなければならないことを意味します。それに基づいて、もう少し制限された型で関数のバージョンを実際に書くことができます。

q' :: ([b] -> b) -> ([((), b)] -> ((), b))

しかし、それはあまり満足のいくものではないと思います。:]

于 2012-10-05T15:13:43.410 に答える
2

これは、新しい署名/インターフェイスを使用すると、今では些細なことではありませんか?

import Data.List (elemIndex)

q v f [] = v
q v f xs = let ys = map snd xs; x = f (snd v) ys in
           case elemIndex x ys of Just i -> xs !! i ; _ -> v 
                                               -- or (fst v, x) if you prefer

制約がsafeMaximumなければノーはありえませんよね？Ordそれで、それは省略でしたか、それとも意図的なものでしたか?

于 2012-10-05T14:38:02.837 に答える
1

その正確な型署名ではありません。たとえば、を選択type b = Double->Doubleして関数[b]->bがfoldr (.) idである場合、ポリモーフィック関数はそこで生成された値を使用してペアから選択するq ことはできませんが、選択の手段を促進/解除するのではなく、特定のタイプのsigを探すと問題を誤解していると思います要素からペアへ。

生の選択問題を解決する

元の関数を使用してリストから要素を選択するだけの場合は、代わりに2つから選択する方法をHaskellに指示できます。

このソリューションは、ヘルパー関数を使用して、元のリストまたはフォールバック要素からの選択を強制するという意味で安全です。b -> b -> Boolここで、Trueは、最初の引数を優先することを示します。

これを使用して、ペアから選択できます。

selectPair :: (a -> a -> Bool) -> (a,c) -> (a,c) -> (a,c)
selectPair f (a,c) (a',c') 
    | f a a'    = (a,c)
    | otherwise = (a',c')

次に、折りたたんでリストから選択します。

selectList :: (a -> a -> Bool) -> (a,c) -> [(a,c)] -> (a,c)
selectList f = foldr (selectPair f)

これはタイプのインスタンスを必要としないことに注意してaください。したがって、一般的な設定で必要になる場合があります。

最大の問題を解決する

もちろん、インスタンスからの(b -> b -> Bool)ように感じます。例では、最大値を提案する関数を使用しましたが、Ordインスタンスがある場合は、インポートを使用して実行するのが最も簡単です。>OrdData.ListData.Function

safePairMaximum :: Ord b => (a, b) -> [(a, b)] -> (a, b)
safePairMaximum m bs = maximumBy (compare `on` snd) $ m:bs

これは、 hammarのソリューションの一部のより基本的でクールではないバージョンです。

たぶんあなたは立ち往生しています-[b]->bですが、bには平等があります

これは、あなたが述べた問題を解決しながら、私が賢明だと思う型注釈にできるだけ近づきます。選択関数を使用すること::[b]->bが重要な場合は、少なくともEqコンテキストが必要になります。

chooseLike :: Eq b => (a, b) -> ([b] -> b) -> ([(a, b)] -> (a, b))
chooseLike m selectb pairs = let wanted = selectb $ map snd pairs in
    case filter ((==wanted).snd) pairs of
      [] -> m
      (p:_) -> p

（もちろん、Eqコンテキストを(b -> b -> Bool)引数に置き換えることができます。今回は平等を示します。）

これは理想的ではありません。[b]リストを個別にリストに移動するため[(a,b)]、非効率的です。

結論

あなたが指定したタイプの便利な機能はないと思いますが、あなたが述べた問題を解決するにはさまざまな方法があります。興味深い質問でした、ありがとう。

于 2012-10-05T15:21:13.803 に答える
1

これが有意義な方法で可能だとは思いません。これは単なる直感であり、証明できないため、反例を示します。

私が関数を持っているとしましょうsum :: Num a => [a] -> a。リストに適用できます：

sum [1 .. 4]
> 10

しかし、「持ち上げられた」を適用したいとしましょうsum:

liftedSum [("abc", 1), ("def", 2), ("ghi", 3), ("jkl", 4)]
> (??WTF??, 10)

どのような意味のある値が必要??WTF??ですか? 思いつきません。

問題は[b] -> b、実際には「集計」を意味する場合もあるのに、「1 つを選択する」と解釈したことです。そして、私がやろうとしていたように、集計関数をタプルに「持ち上げる」意味のある方法はありません。

しかし、別の問題は、「1 つを選択する」という意味であっても、重複する値がある場合、[b] -> bそれを使用して から一意に選択できないことです。例：[(a, b)]b

liftedMax [("abc", 1), ("def", 2), ("ghi", 2)]
> (>> is this "def" or "ghi"? <<, 2)

そのため、私の関数を合理的に実装できるとは思いません。また、Haskell の型システムのおかげで自分を撃つことが難しくなったのは素晴らしいことだと思います。

于 2012-10-05T15:05:49.167 に答える