代码之家 › 专栏 › 技术社区 › Daniel Kaplan

定义我自己的concat

haskell

0

Daniel Kaplan · 技术社区 · 7 年前

我在读一本书,它让我定义我自己的 concat 功能。我在这里的定义是正确的:

concat :: [[a]] -> [a]
concat [] = []
-- concat [[]] = []
concat (xs:xss) = xs ++ (Main.concat xss)

关于这个我有两个问题。

为什么我不需要我评论的那句话?
当我把这个叫做 Main.concat [[]] ,一步一步,怎么评价?我的想法是,它进入了第二个定义,但我无法理解。如果我是对的,这是第二个定义,那么 xs 和 xss 是吗?

3 回复 | 直到 7 年前

1

5

Daniel Wagner 7 年前

如果我是对的,这是第二个定义,那么 xs 和 xss 是吗?

让我们问:

> f (xs:xss) = (xs, xss)
> f [[]]
([],[])

因此,现在尝试将这些值替换为您的定义:

concat (xs:xss) = xs ++ (Main.concat xss)
                = [] ++ (Main.concat [] )
                = [] ++ []
                = []

2

3

Purag 7 年前

[[]] 也可以写成 [] : [] (使用 (:) 构造函数)——也就是说,头为空列表,尾为空列表的列表。这样就可以成功地匹配 xs:xss 是的。

所以匹配后 xs 具有 [] 和 xss 具有 [] ,我们有效地得到以下行为:

let xs = [] in
  let xss = [] in
    xs ++ (Main.concat xss)

通过替换,我们得到

[] ++ (Main.concat [])

递归调用将命中基本情况,从而返回 [] ,给予 [] ++ [] 最终 [] 是的。

3

1

AJF 7 年前

TL/博士: [[]] = [] : [] 就像 [1] = 1 : [] ,所以它与 x:xs 模式。

在haskell中,列表的定义如下:

data [a]    -- a list of `a`s is...
  = []      -- an empty list...
  | a : [a] -- or an `a`, then a list of `a`s.

当我们写作时 [1,2,3] ,这只是 1 : (2 : (3 : [])) ,自 : 我们称之为 右结合 ,我们也可以写 1:2:3:[] 是的。

因此,当在列表上进行模式匹配时,通常只需要两种情况: [] 和 (x:xs) 是的。 [] 显然是空名单,而且 (x:xs) 是一个非空列表,其中 x 是第一个元素 xs 是名单的其余部分。

让我们检查这个定义,忽略注释行。顺便说一下,我去掉了一些不必要的括号:

concat :: [[a]] -> [a]
concat []     = []                  -- The empty list case
concat (x:xs) = x ++ Main.concat xs -- The nonempty list case

我们看到您实际上已经涵盖了所有的案例:现在已经为所有列表定义了这一点,所以至少在理论上 concat [[]] = [] 是多余的。

实际上也是这样,因为 concat [[]] = [] ++ concat [] = [] 不管怎样,这属于第二行的情况,因为 [[]=[]:[] 符合 (x:xs) 模式。