Skip to main content

Problem Sheet for LI Functional Programming - Week 4

用户定义的数据类型 User Defined Data Types​

  1. 定义一个函数 allPositions :: Eq a => a -> [a] -> [Int]，找到一个元素在列表中出现的所有位置。例如，我们应该有 allPositions 17 [13,17,17,666] = [1,2] 和 allPositions 17 [1,2,3] = []。

  2. 回顾一下数据类型

    data WeekDay = Mon | Tue | Wed | Thu | Fri | Sat | Sun
                   deriving (Show, Read, Eq, Ord, Enum)

    在讲义中定义。定义一个新的数据类型，只表示一周中的工作日。证明它是上述类型的一个缩减。

  3. 证明 Maybe a 类型是 [a] 类型的 retract。

  4. 重写前奏中的 head 和 tail 函数，使它们使用 Maybe 类型构造函数来指示何时提供参数为空。

  5. 同样地，重写 take :: Int -> [a] -> [a]，用 Maybe 来表示当索引比列表长时。

  6. Either 类型构造函数的一个常见用途是返回关于可能的错误条件的信息。将前奏中的函数 zip 改写为

    zipEither :: [a] -> [b] -> Either String [(a,b)]

    所以我们只在两个参数的长度相同的情况下得到对的列表。如果不是这种情况，使用 String 来报告哪个参数小。

  7. 定义一种二叉树的类型

    data BinLN a b = ???

    它在每个叶子上携带一个 a 类型的元素，在每个节点上携带一个 b 类型的元素。

  8. 使用前一个问题的数据类型，写一个函数

    leaves :: BinT a b -> [a]

    它收集了装饰给定树的叶子的元素列表。

  9. 实现一个新版本的二叉树，它只在叶子上携带数据。

    data BinL a = ???

  10. 使用前面例子中的数据类型，并假设类型 a 有一个 Show 的实例，实现一个函数，将树渲染成一个括号的集合，包围着叶子上的元素。

    showBin :: Show a => Bin a -> String

    For example:

    *Main> showBin (Nd (Lf 1) (Nd (Lf 3) (Lf 4)))
    "((1)((3)(4)))"

  11. 你能写一个函数，给定这样一个括号内的数字字符串，产生相应的树吗？你可能想用 Maybe 或 Either 来报告这个字符串的格式是否有问题。(你可能想查一下 read 函数，以帮助将字符串转换为整数类型)。

  12. 写一个函数 preOrderTree :: [a] -> [BT a]，其属性为 elem t (preOrderTree xs)，当且仅当 treePreOrder t = xs 适用于所有 t :: Bin a 和 xs :。[a]。

  13. 更难 考虑函数

    g :: Integer -> (Integer -> Bool)
    g y = \x -> x == y

    你是否认为 g 有一个同伴 f : (Integer -> Bool) -> Integer，将函数 Integer -> Bool "解码"为整数，这样，对于整数 y 的任何代码 g y，我们得到的整数是 f (g y) = y？如果是，请给出这样一个 f 的 Haskell 定义，并说服自己，对于所有的整数 y，f (g y) = y。如果不是，为什么？

  14. 更难 写一个函数 breadthFirstTree :: [a] -> [BT a]，其属性为 elem t (breadthFirstTree xs)，当且仅当 treeBreadthFirst t = xs 为所有 t :: Bin a 和 xs :。[a]。解决方案)