是否可以用Haskell或其他函数式语言正式定义下列类型的T?
类型T包含函数,给定X中的对象集合(即一组),为集合中的每个对象分配一个编号。
例如,假设我们有一个来自T的函数T。它的参数arg必须是来自X的对象的集合(集合),例如字符串'abc‘、'def’、'xyz‘的列表。它的返回值必须是一个函数r,它只接受三个可能的参数:'abc'、'def'或'xyz',并返回一个数字。在这种情况下,我特别不希望r只接受任何字符串作为参数。
一个例子可能是“秩函数”,它在给定对象集合的情况下,以某种方式为每个对象分配一个秩。它不只是返回一个数字集合,而是返回一个函数,该函数接受原始集合的任何成员,并返回该成员的级别。
当然,如果我稍微改变一下我的需求,事情就会变得非常简单。我可以要求函数t只接受一个对象集合,并返回一个数字集合。这几乎是,但不是完全一样。这样的定义需要做一些额外的工作:我必须将输入集合中的对象与输出集合中的对象匹配。而且,它也不会那么精确:可能返回的数字集合可能与输入对象不匹配(例如,可能有一个数字太多)。
如果我所描述的约束不能表示为类型约束,并且应该以不同的方式强制执行,我不会感到惊讶。
编辑:我最初还要求定义一个类型的U,它包含将一个函数从X转换为数字的函数,并返回一个T类型的函数。但我没有很好地解释这一点,这只会使我的问题更加混乱。所以最好忽略我问题的这一部分。
发布于 2012-09-18 11:13:09
编辑:根据更新的问题,我已经完全重写了这个答案。
忽略对类型的强调,采取一种实用的方法,让我们开始在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是一个单一的优点,它可以被认为是可能失败的计算。这样您就可以像这样轻松地链接调用。
*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但是,这不仅没有实际价值,而且没有精确地确定这些功能。基于对的方法也不是。在我的经验中,试图构造高度限制性的类型,比如只包含['abc', 'def', 'xyz']中的值的类型,是不太实际的。
发布于 2012-09-18 11:55:01
T标记
好的,我想重命名你的类型,以帮助理解它们。T将数字分配给值,因为我不确定容器的结构是什么(并且希望保持灵活性),所以我将在一对(x,n)中弹出这个值和数字。让我们称其为标记,所以请重新命名T Tagger,因此假设我知道您的集合类型是Coll,那么X的集合将具有Coll 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参数化了。
为了提高代码重用性,我倾向于用类型参数(比如某些语言中的泛型)替换固定类型的X和集合类型的Coll:
data (Functor coll,Num n) => Tagger coll x n = Tgr (coll x -> coll (x,n))因此,现在我们坚持认为coll选择类型是一个函子,所以我们可以使用fmap对集合应用函数点态(在您的情况下至关重要,任何集合类型都是函子的一个实例)。
对于Tagger的定义,T是我最高兴的,但是如果您只有coll、x和n的一种可能性,您可以使用CollTaggerXInt。
制U塔格器
您的U类型用于将元素级taggers转换为集合taggers。我想叫它Lift,而不是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因此,我们可以将它与coll作为f,x作为a,(x,n)作为b,并定义
liftT :: (Functor coll,Num n) => (x -> n) -> coll x -> coll (x,n)
liftT f = fmap tag where
tag x = (x,f x)如果您想定义您的类型,好的,但是我认为liftT可能是您的类型U中唯一合理的函数。
秩- U+Context
现在我认为你的排名例子很有用,所以让我们来研究一下。秩函数需要检查集合的所有元素,所以让我们将整个集合作为它的第一个参数,所以是rankfunction :: coll x -> x -> n (在上下文(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)传递它的第一个参数--整个集合--然后使用liftT将其应用于每个元素。这被称为部分评估,对于这类事情来说非常方便。
发布于 2012-09-18 19:31:00
如果您想要一个接受值并返回类型(除其他外)的函数,则需要依赖类型。你可以在哈斯克尔模拟依赖类型,但它不漂亮。
https://stackoverflow.com/questions/12475690
复制相似问题