# Solutions to the Problem Sheet for LI Functional Programming - Week 4

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

1. 定义一个函数 allPositions :: Eq a => a -> [a] -> [Int]，找到一个元素在一个列表中出现的所有位置。

haskellallPositions :: Eq a => a -> [a] -> [Int]allPositions a as = snd (foldr f (length as - 1,[]) as)  where f x (i,r) | x == a = (i-1,i:r)                  | otherwise = (i-1,r)
2. 定义一个新的数据类型，只表示一周中的个工作日。证明它是 WeekDay 类型的一个缩减。

data WorkingDay = Mon' | Tue' | Wed' | Thu' | Fri'  deriving (Eq, Show)toWeekDay :: WorkingDay -> WeekDaytoWeekDay Mon' = MontoWeekDay Tue' = TuetoWeekDay Wed' = WedtoWeekDay Thu' = ThutoWeekDay Fri' = FritoWorkingDay :: WeekDay -> WorkingDaytoWorkingDay Mon = Mon'toWorkingDay Tue = Tue'toWorkingDay Wed = Wed'toWorkingDay Thu = Thu'toWorkingDay Fri = Fri'toWorkingDay Sat = Fri'toWorkingDay Sun = Mon'
3. 证明 Maybe a 类型是 [a] 类型的缩减。

toList :: Maybe a -> [a]toList Nothing = []toList (Just x) = [x]toMaybe :: [a] -> Maybe atoMaybe [] = NothingtoMaybe (x:_) = Just x
4. 重写前奏中的 headtail 函数，使它们使用 Maybe 类型构造函数来指示何时提供参数为空。

headMaybe :: [a] -> Maybe aheadMaybe [] = NothingheadMaybe (x:_) = Just xtailMaybe :: [a] -> Maybe [a]tailMaybe [] = NothingtailMaybe (_:xs) = Just xs
5. 同样地，重写 take :: Int -> [a] -> [a]，用 Maybe 来表示当索引比列表长时。

takeMaybe :: Int -> [a] -> Maybe [a]takeMaybe n [] | n == 0 = Just []               | otherwise = NothingtakeMaybe n (x:xs) =  case takeMaybe (n-1) xs of    Nothing -> Nothing    Just r -> Just (x:r)
6. 重写前奏中的函数 zip，以便我们只在两个参数的长度相同时得到对的列表。如果不是这种情况，使用 String 来报告哪个参数小。

zipEither :: [a] -> [b] -> Either String [(a,b)]zipEither [] [] = Right []zipEither [] (_:_) = Left "Left list too small"zipEither (_:_) [] = Left "Right list too small"zipEither (x:xs) (y:ys) =  case zipEither xs ys of    Left msg -> Left msg    Right r -> Right ((x,y):r)
7. 定义一个二叉树的类型，在每个叶子上携带一个 a 类型的元素，在每个节点上携带一个 b 类型的元素。

data BinLN a b = Leaf a | Node (BinLN a b) b (BinLN a b)
8. 使用前一个问题的数据类型，写一个函数，收集装饰给定树的叶子的元素列表。

leaves :: BinLN a b -> [a]leaves (Leaf x) = [x]leaves (Node l _ r) = leaves l ++ leaves r
9. 实现一个新版本的二叉树，它只在叶子上携带数据。

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

showBin :: Show a => BinL a -> StringshowBin (Lf a) = "(" ++ show a ++ ")"showBin (Nd l r) = "(" ++ showBin l ++ showBin r ++ ")"
11. 你能写一个函数，给定这样一个括号内的数字字符串，产生相应的树吗？你可能想用 MaybeEither 来报告这个字符串的格式是否有问题。(你可能想查一下 read 函数，以帮助将字符串转换为整数类型)。

type MaybeReader a = String -> Maybe (a,String)mrInt :: MaybeReader IntmrInt s = case reads s of  [(i,r)] -> Just (i,r)  _ -> NothingmrLeftParen :: MaybeReader ()mrLeftParen ('(':r) = Just ((),r)mrLeftParen _ = NothingmrRightParen :: MaybeReader ()mrRightParen (')':r) = Just ((),r)mrRightParen _ = NothingmrSeq :: MaybeReader a -> MaybeReader b -> MaybeReader (a,b)mrSeq x y s =  case x s of    Nothing -> Nothing    Just (a,r) ->      case y r of        Nothing -> Nothing        Just (b,q) -> Just ((a,b),q)mrChoice :: MaybeReader a -> MaybeReader b -> MaybeReader (Either a b)mrChoice x y s =  case x s of    Nothing -> case y s of                 Nothing -> Nothing                 Just (b,r) -> Just (Right b, r)    Just (a,r) -> Just (Left a , r)mrParens :: MaybeReader a -> MaybeReader amrParens x s =  case (mrLeftParen mrSeq (x mrSeq mrRightParen)) s of    Nothing -> Nothing    Just (((),(a,())),r) -> Just (a,r)parseLeaf :: MaybeReader (BinL Int)parseLeaf s = case mrParens mrInt s of  Nothing -> Nothing  Just (i,r) -> Just (Empty i,r)parseBranch :: MaybeReader (BinL Int)parseBranch s =  let br = mrParens (parseBin mrSeq parseBin) in    case br s of      Nothing -> Nothing      Just ((l,r),rem) -> Just (Branch l r , rem)parseBin :: MaybeReader (BinL Int)parseBin s =  case mrChoice parseLeaf parseBranch s of    Nothing -> Nothing    Just (Left b,r) -> Just (b,r)    Just (Right b,r) -> Just (b,r)
12. 写一个函数 preOrderTree :: [a] -> [BT a]，其属性为 elem t (preOrderTree xs)，当且仅当 treePreOrder t = xs 适用于所有 t :: Bin axs :。[a].

hspreOrderTree :: [a] -> [BT a]preOrderTree [] = [Empty]preOrderTree xs = [Fork x l r | i <- [1..length xs],    let (x:zs, ys) = splitAt i xs,    l <- preOrderTree zs, r <- preOrderTree ys]
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 定义，并说服自己，对于所有的整数 yf (g y) = y。如果不是，为什么？

答案 这实际上是不可能的。可以证明这样一个函数 f 的存在允许解决停顿问题，而这个问题已知是无法解决的。

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

A solution can be found at the provided link.