2

T可以用 Haskell 或其他函数式语言正式定义以下类型吗？

类型T包含函数，给定来自 的对象集合（即一组） ，为该集合中的每个对象X分配一个数字。

例如，假设我们有一个函数tfrom T。它的参数arg必须是来自 的对象的集合（集合）X，例如字符串列表 ['abc', 'def', 'xyz']。它的返回值必须是一个r只接受三个可能参数的函数：'abc'、'def'或'xyz'，并返回一个数字。在这种情况下，我特别不想r接受任何字符串作为参数。

一个例子可能是“等级函数”，它给定一组对象，以某种方式为每个对象分配一个等级。它不只返回一组数字；相反，它返回一个函数，该函数采用原始集合的任何成员，并返回该成员的等级。

当然，如果我稍微改变一下我的要求，事情就会变得超级简单。我可以要求该函数t只接受一组对象并返回一组数字。这差不多，但不完全相同。这样的定义需要一些额外的工作：我必须将输入集合中的对象与输出集合中的对象进行匹配。而且它也不会那么精确：返回的数字集合可能与输入对象不匹配（例如，一个数字可能太多）。

如果我所描述的约束不能表达为类型约束，我不会感到惊讶，并且应该以不同的方式强制执行。

编辑：我最初还要求定义一个类型，该类型U包含将函数从X数字转换为数字的函数，并返回 type 的函数T。但我没有很好地解释这一点，它只会给我的问题增加困惑。所以最好忽略我问题的这一部分。

4

3 回答 3

1

编辑：鉴于问题的更新，我已经完全重写了这个答案。

暂时忽略对类型的强调并采取实用的方法，让我们开始在 Haskell 中构建此功能。首先，这是一个函数，给定一个函数、一个对象列表和一个对象，如果该对象在列表中，则将该函数应用于该对象。

u f list x = assert (x `elem` list) $ f x

（assert 函数来自Control.Exception）这也可以通过一个守卫来实现：

u f list x | (x `elem` list) = f x --similar but gives a slightly different error msg

在 ghci 中运行一些示例会得到以下结果：

*Main> u (+1) [1,2,3] 1
2
*Main> u (+1) [1,2,3] 2
3
*Main> u (+1) [1,2,3] 3
4
*Main> u (+1) [1,2,3] 4
*** Exception: test.hs:3:14-19: Assertion failed

但是，这不是非常安全的代码，因为没有静态保证不会以这种方式调用函数而导致崩溃。

另一种方法是使用Maybe类型。

u' f list x = if elem x list then Just (f x) else Nothing

它具有以下行为：

*Main> u' (+1) [1,2,3] 2
Just 3
*Main> u' (+1) [1,2,3] 3
Just 4
*Main> u' (+1) [1,2,3] 4
Nothing

这仍然不能静态地保证不会以不正确的方式调用函数，但它确实静态地保证基于返回值的任何结果必须同时处理Just result和Nothing。这也带来Maybe了 monad 的优势，可以将其视为可能失败的计算。所以你可以像这样轻松地链接调用

*Main> let func = u' (+1) [1,2,3]
*Main> func 1
Just 2
*Main> func 1 >>= func
Just 3
*Main> func 1 >>= func >>= func
Just 4
*Main> func 1 >>= func >>= func >>= func
Nothing

这似乎是在 Haskell 中解决此类问题的最佳实用方法。但是，问题询问是否有一种类型专门确定这样的功能。让我们看看这些函数的类型：

u  :: Eq x => (x -> a) -> [x] -> x -> a
u' :: Eq x => (x -> a) -> [x] -> x -> Maybe a

这两种类型都不要求列表的成员资格使它们工作与否。我能想到的将其作为一种类型工作的唯一方法是将集合本身​​视为一种类型。调用那个类型col，然后我们可以做

u :: (col -> x) -> col -> x

但这不仅没有什么实用价值，而且也没有精确地确定这些功能。基于对的方法也没有。根据我的经验，尝试构建高度限制性的类型（例如仅包含 in 值的类型['abc', 'def', 'xyz']）并不是很实用。

于 2012-09-18T11:13:09.183 回答
1

T - 标记

好的，我想重命名您的类型以帮助理解它们。T将数字分配给值，并且由于我不确定容器的结构是什么（并且希望保持灵活），因此我将在 pair 中弹出值和数字(x,n)。让我们称之为标记，所以 rename T Tagger，所以假设我知道你的集合类型是sColl的集合，所以我需要XColl X

type CollTaggerXInt = Coll X -> Coll (X,Int)

这使您想要的功能成为类型同义词。

但是，如果Int太小而您想使用Integer，或Double其他数字类型怎么办？

data Num n => CollTaggerX n = CollTaggerX (Coll X -> Coll (X,n))

这意味着您可以X使用任何固定类型的数值数据来标记值。（Num n =>是断言 n 必须是数字类型的数据类型约束。）右侧的 CollTaggerX 通过将标记函数包装在轻量级构造函数中来确保类型安全。我们需要使用data，而不是type因为我已经参数化了n.

我倾向于用类型参数（如某些语言中的泛型，例如 Java）替换固定类型X和集合类型Coll，以提高代码重用：

data (Functor coll,Num n) => Tagger coll x n = Tgr (coll x -> coll (x,n))

因此，现在我们坚持认为collction 类型是 Functor，因此我们可以使用fmap将函数逐点应用于集合（在您的情况下至关重要，任何集合类型都将是 Functor 的实例）。

我对Taggerfor your 的定义最满意T，但CollTaggerXInt如果您只有一种可能性，您可以使用coll,x和n。

U - 制作标签

您的U类型是将元素标记器转换为集合标记器。我想称之为Lifting，而不是U. 如果您正在使用CollTaggerXInt，则可以再次使用类型同义词：

type LiftXIntToTagger = (X -> Int) -> Coll X -> Coll (X,Int)

或者如果您使用更灵活的Tagger定义，您可以编写

data (Functor coll,Num n) => Lifter coll x n = Lifter ((x -> n) -> coll x -> coll (x,n))

但这一切都让人觉得为此创建一个类型很疯狂，因为如果你有一个逐点函数，你可以使用它来提升它无论如何fmap都适用于你的类型：coll

fmap :: Functor f => (a -> b) -> f a -> f b

所以我们可以将它与collas f、xasa和(x,n)as b 一起使用，并定义

liftT :: (Functor coll,Num n) => (x -> n) -> coll x -> coll (x,n)
liftT f = fmap tag   where 
      tag x = (x,f x)

如果你想定义你的类型，好的，但我认为liftT这可能是你的 type 中唯一合理的函数U。

排名 - U+上下文

现在我认为您的排名示例很有用，因此让我们对此进行调查。rankfunction 需要检查集合的所有元素，所以让我们给它整个集合作为它的第一个参数，所以rankfunction :: coll x -> x -> n（在 ​​context 中(Functor coll,Num n)）。

liftInContext :: (Functor coll,Num n) => (coll x -> x -> n) -> coll x -> coll (x,n)
liftInContext rankfunction mycoll = liftT (rankfunction mycoll) mycoll

在这里，该函数(rankfunction mycoll)将其第一个参数——整个集合——传递给 rankfunction，然后使用 liftT 将其应用于每个元素。这称为部分评估，对于这类事情非常方便。

于 2012-09-18T11:55:01.047 回答
0

如果你想要一个接受一个值并返回一个类型（除其他外）的函数，你将需要依赖类型。您可以在 Haskell 中模拟依赖类型，但它并不漂亮。

于 2012-09-18T19:31:00.513 回答