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从对列表中获取第二个元素最大的对：

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. 如果我们有一个 type 的函数，我们可以从它得到所需的类型[f b] -> f [b]，它看起来很像sequence.

f考虑一下is的情况((->) a)：给定一个函数[b] -> b和一个列表[a -> b]，我们可以返回一个函数a -> b，它将其类型的参数应用于a列表中的每个函数，使用选择器函数，然后返回类型的结果b。这听起来像你所追求的！

不幸的是，它不适用于您的特定示例-Monad涉及的是 writer monad，它将添加一个Monoid约束并始终返回列表中每个值a的 monoid 总和。a

它失败的原因是我们只有一个不透明的b值选择函数，必须在没有任何上下文的情况下使用它，这需要使用类似sequence提取（并在过程中合并）所有单独的上下文的东西。要编写所需的函数，您需要一种方法来合并上下文，而不会丢失将上下文与每个元素相关联的信息。

reader monad 可以在其他人不使用的地方工作，因为所涉及的“合并”过程是唯一的——将单个参数应用于多个函数是基于对 and 给出的规范 comonoid 的逆变使用\x -> ()，\x -> (x, x)其中每个结果元素唯一地确定原始输入.

为了在协变位置获得相同的属性，我们需要一个幺半群，其中每个输入元素唯一地确定结果和，这意味着每个输入必须相同，这意味着它们必须是只有一个值的类型。基于此，我们确实可以编写一个类型稍微受限的函数版本：

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

我不相信这是可能的有意义的方式。由于这只是直觉，我无法证明，我只举一个反例：

假设我有这个功能sum :: Num a => [a] -> a。我可以将其应用于列表：

sum [1 .. 4]
> 10

但是，假设我想应用我的 'lifted' sum：

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

应该有什么有意义的价值??WTF??？我想不出一个。

问题是我将其解释[b] -> b为“选择一个”，而实际上，它也可能意味着“聚合”。正如我试图做的那样，没有任何有意义的方法可以将聚合函数“提升”为元组。

但另一个问题是，即使意味着“选择一个” ，如果存在重复值[b] -> b，您也不能使用它来唯一地选择 from 。例子：[(a, b)]b

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

所以我不认为我的功能可以合理地实现，而且我认为 Haskell 的类型系统让我很难在脚下射击自己，这很酷。

于 2012-10-05T15:05:49.167 回答
1

没有那个确切的类型签名，不。例如，如果您选择type b = Double->Double并且您的函数[b]->b是foldr (.) id，那么您的多态函数q 不能使用那里产生的值从对中进行选择，但我认为这会将您的问题误解为寻求特定类型的 sig，而不是提升/提升选择方式从元素到对。

解决原始选择问题

如果您的原始函数仅用于从列表中选择一个元素，您可以告诉 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)

请注意，这不需要 type 上的任何实例a，因此可能是您在一般设置中所需要的。

解决最大问题

当然(b -> b -> Bool)感觉很像>来自一个Ord实例，并且您的示例使用了一个建议最大值的函数，但是如果您有一个 Ord 实例，那么使用 importData.List和Data.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 回答