Haskell中的类型条件控件

Question

我正在解决99个Haskell问题,以提高我对该语言的熟练程度.在问题7("展平嵌套列表结构")中,我发现自己想要根据传递给函数的参数类型定义条件行为.也就是说,因为

*Main> :t 1
1 :: (Num t) => t
*Main> :t [1,2]
[1,2] :: (Num t) => [t]
*Main> :t [[1],[2]]
[[1],[2]] :: (Num t) => [[t]]

(即嵌套在不同级别的列表具有不同的数据类型)似乎我应该能够编写一个可以读取参数类型的函数,然后相应地表现.我的第一次尝试就是这样:

listflatten l = do
    if (:t l) /= ((Num t) => [t]) then
        listflatten (foldl (++) [] l)
        else id l

但是当我尝试这样做时,Haskell返回一个解析错误.Haskell是否足够灵活以允许这种类型操作,我是否需要找到另一种方法？

Answer 1

1.改用模式匹配

您可以在不动态检查数据类型的情况下解决该问题.事实上,在Haskell中很少需要它.通常您可以使用模式匹配.

例如,如果您有类型

data List a = Elem a | Nested [List a]

你可以模仿匹配

flatten (Elem x) = ...
flatten (Nested xs) = ...

例:

data List a = Elem a | Nested [List a]
  deriving (Show)

nested = Nested [Elem 1, Nested [Elem 2, Elem 3, Nested [Elem 4]], Elem 5]
main = print $ flatten nested

flatten :: List a -> [a]
flatten (Elem x) = [x]
flatten (Nested lists) = concat . map flatten $ lists  

map flatten扁平化每个内部列表,因此它的行为类似[List a] -> [[a]],我们在此处生成列表列表.concat将所有列表合并在一起(concat [[1],[2,3],[4]]给出[1,2,3,4]).concat . map flatten是一样的concatMap flatten.

2.要动态检查类型,请使用Data.Typeable

如果在某些罕见的情况下(不是在这个问题中)你真的需要动态检查类型,你可以使用Data.Typeable类型类及其typeOf功能.:t仅适用于GHCI,它不是语言的一部分.

ghci> :m + Data.Typeable
ghci> typeOf 3 == typeOf "3"
False
ghci> typeOf "a" == typeOf "b"
True

可能,您还需要使用DeriveDataTypeable扩展.

Answer 2

(抱歉长度 - 我走得有点远/深度过深.CliffsNotes版本是"不,你不能真正做你想要的,因为类型不是价值观,我们不能给你的功能一个明智的类型;使用你自己的数据类型.".第一段和第五段,不计算这个或代码块,解释我的意思的第一部分的核心,其余的答案应该提供一些澄清/细节.)

粗略地说,不,这是不可能的,原因有两个.第一个是类型调度问题.该:t命令是GHCi的一个特性(非常有用),并不是Haskell函数.想想为什么:它会有什么类型？ :t :: a -> ?？类型本身不是值,因此没有类型.这是两个不同的世界.所以你尝试这样做的方式是不可能的.另请注意,您有一个随机的do.这是坏的 - do符号是monadic计算的语法糖,你没有做任何这些.摆脱它!

为什么是这样？Haskell有两种多态性,我们现在关注的是参数多态.当你有类似的类型时,这就是你所看到的concat :: [[a]] -> a.这a表示从现在到结束时concat,每个可能的一个单一定义必须可用a.你怎么flatten用这个方案打字？这是不可能的.

您正在尝试为不同类型的数据调用另一个为ad-hoc定义的函数.这被称为令人震惊的ad-hoc多态性.例如,在C++中,您可以定义以下函数:

template <typename T>
void flatten(vector<T>& v) { ... }

template <typename T>
void flatten(vector< vector<T> >& v) { ... }

这将允许您针对不同类型执行不同的操作.你甚至可以拥有template <> void flatten(int) { ... }!你可以在Haskell中使用类型类来实现这一点,例如:Num或Show; 类型签名的整个要点Show a => a -> String就是可以为不同的as 调用不同的函数.事实上,你可以利用这个来获得问题的部分解决方案......但在我们做之前,让我们来看看第二个问题.

此问题与您尝试提供的列表有关.Haskell的列表类型定义为(粗略)data [a] = [] | a : [a].换句话说,列表的每个元素必须具有相同的类型; 一个整数列表[Int],仅包含整数Int; 以及整数列表[[Int]],仅包含整数列表,[Int].结构[1,2,[3,4],5]是非法的!阅读你的代码,我想你明白这一点; 然而,还有另一种衍生物.出于类似的原因,您无法编写类型的完全通用的展平函数flatten :: [...[a]...] -> [a].您的函数还必须能够处理任意嵌套深度,这对于列表仍然是不可能的.你需要[a],[[a]]等等都属于同一类型!

因此,要获得所有必需的属性,您需要一个不同的类型.您想要的类型具有不同的属性:它包含任何内容,单个元素后跟值的其余部分,或嵌套的元素列表,后跟剩余的值.换句话说,就像

data NList a = Nil
             | a         :>  NList a
             | (NList a) :>> NList a
             deriving (Eq, Show)
infixr 5 :>, :>>

然后,[1,2,3] == 1 : 2 : 3 : []你会写,而不是列表1 :> 2 :> 3 :> Nil; (1 (2 3) 4 ())你会写, 而不是Lisp 1 :> (2 :> 3 :> Nil) :>> 4 :> Nil :>> Nil.您甚至可以开始定义操作它的函数:

nhead :: NList a -> Either a [a]
nhead Nil       = error "nhead: Empty NList."
nhead (h :>  _) = Left  a
nhead (h :>> _) = Right a

ntail :: NList a -> NList a
ntail Nil       = error "nhead: Empty NList."
ntail (_ :>  t) = t
ntail (_ :>> t) = t

不可否认,您可能会发现这有点笨拙(或许不是),所以您可能会尝试以不同的方式考虑您的类型.另一个选项,即99个问题的Haskell转换使用,是要意识到嵌套列表中的所有内容都是单个项目或嵌套列表列表.这个翻译给你

data NestedList a = Elem a
                  | List [NestedList a]
                  deriving (Eq, Show)

然后上面两个列表成为List [Elem 1, Elem 2, Elem 3]和List [Elem 1, List [Elem 2, Elem 3], Elem 4, List []].至于如何压扁它们 - 因为你试图从99个问题中学习,我不会说:)毕竟,你似乎已经解决了问题的这一部分.

现在,让我们回到类型类.当我说你不能写出一个任意嵌套列表的东西时,我撒了一点 - 事实上,你可以使用类型类和一些GHC扩展.现在,在我继续之前,我应该说:不要使用它! 认真.另一种技术几乎肯定是更好的选择.但是,这种技术很酷,所以我将在这里介绍.请考虑以下代码:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, UndecidableInstances #-}

class Flattenable f e where
  flatten :: f -> [e]

instance Flattenable a a where
  flatten = return

instance Flattenable f e => Flattenable [f] e where
  flatten = concatMap flatten

我们正在创建一个类型类,其实例是我们可以展平的东西.如果我们有Flattenable f e,那么f应该是一个集合,在这种情况下是一个列表,其元素最终是类型e.任何单个对象都是这样的集合,其元素类型本身; 因此,第一个实例声明允许我们将任何内容展平为单个列表.第二个实例声明说,如果我们可以f将一个es 压缩成一个列表,那么我们也可以通过展平每个fs将一个列表es压缩成一个s 列表f并将结果列表粘在一起.这种递归类定义递归定义的函数嵌套列表类型,使您能够压平嵌套列表与单功能的能力flatten:[1,2,3],[[4,5],[6]],[[[7,8],[9]],[[10]],[[11],[12]]],等等.

但是,由于多个实例等,它确实需要单个类型的注释:例如,您需要编写flatten [[True,False],[True]] :: [Bool].如果你的列表中有类型为class-polymorphic的东西,那么事情会更严格一些; 你需要写flatten [[1],[2,3 :: Int]] :: [Int],而据我所知,结果列表本身不能是多态的.(但是,我最后一部分可能是错的,因为我没有尝试过任何方式.)由于类似的原因,这太开放了 - instance Flattenable [f] () where flatten = [()]如果你也愿意,你可以声明.我试图让类型系列/功能依赖项工作以解决其中的一些问题,但由于递归结构,无法让它工作(我没有e和一个声明的type Elem a = a和type Elem [f] = Elem f,但这些冲突,因为[f]匹配a).如果有人知道怎么做,我非常想看到它!

再一次,抱歉长度 - 当我累了的时候,我往往会开始喋喋不休.不过,我希望这有用!

Answer 3

您:t将解释器中的交互式命令与内置函数混淆.您无法在运行时查询类型.