Skip to main content

Problem Sheet for LI Functional Programming - Week 7 & 8

Important note about running the template on Jupyter​

本周的问题有一个模板，你可以用它来开始。为了使用它，你需要启用 random 和 mtl 包。在 Jupyter 上，你可以在 ghci 中用以下命令来完成这个任务

:set -package mtl
:set -package random

另外，你可以在启用这些软件包的情况下运行 ghci，方法如下。

ghci -package mtl -package random Week7.hs

将 Template-Week7.hs 复制到 Week7.hs 后。

Type Constructors and Functors​

一个类型构造器是一个关于类型的函数。也就是说，给定一个抽象类型 a，它产生一个依赖于 a 的新类型。你已经见过很多例子了。这里只是一些例子。

type F1 a = Maybe a
type F2 a = Either a String
type F3 a = [ a ]
type F4 a = BinT a
type F5 a = Int -> a
type F6 a = (a -> Int) -> Int
type F7 a = RoseT a
type F8 a = ThreeT a

你可以在模板中找到 BinT a、RoseT a 和 ThreeT a 类型的定义。

我们说一个类型构造器是一个向量，如果在两个输入类型之间给定一个函数 f :: a -> b，我们可以产生一个函数 fmap f :: FN a -> FN b 在输出类型之间。

这个想法被 haskell 类型类 Functor 所封装。

class Functor f where
 fmap :: (a -> b) -> f a -> f b

在这个定义中，f 是一个抽象的类型构造函数。

Problem​

  • 为上述所有的类型构造器实现函数 fmap。模板可能是一个有用的起点。

  • You may get the impression from this list that every type constructor is a functor. What happens when you try to implement fmap for dual of F5 from above? That is, for the type constructor hs type NotAFunctor a = a -> Int

Implementing Monads​

  1. 上面所有的类型构造函数 F1、F2、F3、F5 和 F6 都是单体。试着为它们找到尽可能多的实现。

  2. (Adapted from Programming in Haskell) Consider the following simple expression type:

    data Expr a = Var a | Val Int | Add (Expr a) (Expr a)
    deriving Show

    证明它是一个单体。在这种情况下，>>= 函数到底做什么？

Using Monads​

  1. 回顾一下玫瑰树的类型。

    data Rose a = Br (a, [ Rose a ])

    使用 State 单体来实现一个函数

    labelRose :: Rose a -> Rose (Int,a)

    它用一个 fresh 索引来装饰树中的每个节点。

  2. 使用 IO 单体从用户那里读取一行输入并打印一个响应。

  3. 创建一个简单的 REPL，读取一行文本并打印同一行的文字，并将其反转。你可能想查一下 haskell 的 prelude 函数 words 和 unwords。当用户输入空行时，该程序应退出。

A Picking Monad​

你可能还记得注释，Quicksort 的一种形式很容易用 Haskell 写。

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort [l | l <- xs, l < x]
           ++ [x]
           ++ qsort [r | r <- xs, r >= x]

然而，这种实现方式—在递归的情况下，我们总是挑选列表中的第一个元素作为 "枢轴"—有一个严重的缺陷，它导致了在几乎排序（或反向排序）的列表上的 O(n²) 运行时间。实现 Quicksort 的一个更好的方法，预期运行时间为 O(n log n)，就是在列表中随机抽取一个元素作为支点。

为了封装挑选支点的动作，让我们引入一类 "picking monad"。

class Monad m => PickingMonad m where
  pick :: Int -> Int -> m Int

挑选单体包括普通单体的所有操作（return 和 >>=），但也有一个操作 pick lo hi，其预期解释是它应该以某种方式在 lo 和 hi 之间挑选一个数字（即 lo <= pick lo hi <= hi）（比如通过调用随机数生成器，或返回它们的平均值）。

Problem: Implement a new version of Quicksort

qsort :: (Ord a, PickingMonad m) => [a] -> m [a]
qsort = undefined

它对 pick 进行了适当的调用，以选择支点。你的新版本应该。

  1. 鉴于 pick lo hi 的实现总是返回 lo 和 hi 之间的均匀随机数，预计运行时间为 O(n log n)
  2. 在给定的 pick lo hi 的实现中，总是返回 lo，其行为等同于原始版本。

为了测试的目的，你可能会发现考虑以下 PickingMonad 的实例是很方便的，它们分别通过调用系统随机数生成器或总是返回 lo 来实现 pick lo hi。

instance PickingMonad IO where
 pick lo hi = getStdRandom (randomR (lo, hi))

instance PickingMonad Identity where
 pick lo hi = Identity lo

Examples:

> qsort [10,9..1] :: IO [Integer]
[1,2,3,4,5,6,7,8,9,10]
> qsort [10,9..1] :: Identity [Integer]
Identity [1,2,3,4,5,6,7,8,9,10]