Solutions to the Problem Sheet for LI Functional Programming - Week 4
用户定义的数据类型 User Defined Data Types
定义一个函数
allPositions :: Eq a => a -> [a] -> [Int]，找到一个元素在一个列表中出现的所有位置。```haskell
allPositions :: 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)
```定义一个新的数据类型，只表示一周中的个工作日。证明它是
WeekDay类型的一个缩减。data WorkingDay = Mon' | Tue' | Wed' | Thu' | Fri'
deriving (Eq, Show)
toWeekDay :: WorkingDay -> WeekDay
toWeekDay Mon' = Mon
toWeekDay Tue' = Tue
toWeekDay Wed' = Wed
toWeekDay Thu' = Thu
toWeekDay Fri' = Fri
toWorkingDay :: WeekDay -> WorkingDay
toWorkingDay Mon = Mon'
toWorkingDay Tue = Tue'
toWorkingDay Wed = Wed'
toWorkingDay Thu = Thu'
toWorkingDay Fri = Fri'
toWorkingDay Sat = Fri'
toWorkingDay Sun = Mon'证明
Maybe a类型是[a]类型的缩减。toList :: Maybe a -> [a]
toList Nothing = []
toList (Just x) = [x]
toMaybe :: [a] -> Maybe a
toMaybe [] = Nothing
toMaybe (x:_) = Just x重写前奏中的
head和tail函数，使它们使用Maybe类型构造函数来指示何时提供参数为空。headMaybe :: [a] -> Maybe a
headMaybe [] = Nothing
headMaybe (x:_) = Just x
tailMaybe :: [a] -> Maybe [a]
tailMaybe [] = Nothing
tailMaybe (_:xs) = Just xs同样地，重写
take :: Int -> [a] -> [a]，用Maybe来表示当索引比列表长时。takeMaybe :: Int -> [a] -> Maybe [a]
takeMaybe n [] | n == 0 = Just []
| otherwise = Nothing
takeMaybe n (x:xs) =
case takeMaybe (n-1) xs of
Nothing -> Nothing
Just r -> Just (x:r)重写前奏中的函数
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)定义一个二叉树的类型，在每个叶子上携带一个
a类型的元素，在每个节点上携带一个b类型的元素。data BinLN a b = Leaf a | Node (BinLN a b) b (BinLN a b)使用前一个问题的数据类型，写一个函数，收集装饰给定树的叶子的元素列表。
leaves :: BinLN a b -> [a]
leaves (Leaf x) = [x]
leaves (Node l _ r) = leaves l ++ leaves r实现一个新版本的二叉树，它只在叶子上携带数据。
data BinL a = Lf a | Nd (BinL a) (BinL a)使用前面例子中的数据类型，并假设类型
a有一个Show的实例，实现一个函数，将树渲染成一个括号的集合，包围着叶子上的元素。showBin :: Show a => BinL a -> String
showBin (Lf a) = "(" ++ show a ++ ")"
showBin (Nd l r) = "(" ++ showBin l ++ showBin r ++ ")"你能写一个函数，给定这样一个括号内的数字字符串，产生相应的树吗？你可能想用
Maybe或Either来报告这个字符串的格式是否有问题。(你可能想查一下read函数，以帮助将字符串转换为整数类型)。type MaybeReader a = String -> Maybe (a,String)
mrInt :: MaybeReader Int
mrInt s = case reads s of
[(i,r)] -> Just (i,r)
_ -> Nothing
mrLeftParen :: MaybeReader ()
mrLeftParen ('(':r) = Just ((),r)
mrLeftParen _ = Nothing
mrRightParen :: MaybeReader ()
mrRightParen (')':r) = Just ((),r)
mrRightParen _ = Nothing
mrSeq :: 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 a
mrParens 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)写一个函数
preOrderTree :: [a] -> [BT a]，其属性为elem t (preOrderTree xs)，当且仅当treePreOrder t = xs适用于所有t :: Bin a和xs :。[a].```hs
preOrderTree :: [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]
```更难 考虑到函数
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。如果不是，为什么？答案 这实际上是不可能的。可以证明这样一个函数
f的存在允许解决停顿问题，而这个问题已知是无法解决的。更难 写一个函数
breadthFirstTree :: [a] -> [BT a]，其属性为elem t (breadthFirstTree xs)，当且仅当treeBreadthFirst t = xs为所有t :: Bin a和xs :。[a].A solution can be found at the provided link.