沉痛哀悼7月18日京都动画第一工作室纵火案罹难者。

MENU

【代码札记】The Day I Learned Haskell 4

December 9, 2018 • Read: 156 • 瞎折腾阅读设置

这次发的是Homework 3的练习。

代码高尔夫!1

这次的任务很简单:下面有三个任务。对于每个任务,你都应该按照给定名称和类型标识符提交一个对应的尽可能简短的函数。

规则

  • 除了代码,你的解答必须包含一些解释性的注释。没有注释将会取得0分。博主注:我将在下面利用说明性的文本代替注释。你的注释应当完全展示出你对你的答案的理解。换句话说,一切都很公平,但是你必须证明你理解你写的代码。如果有疑问,那么就在注释中包含更多细节。
  • 注释将不会计入你解答的总长度
  • 类型标识不计入解答的总长度
  • import声明不计入解答的总长度。因此你可以随意引用Haskell平台的包。
  • 空白不会计入解答的总长度。所以你没必要将你的代码全部挤在一行里。适时地使用空格,但同时保持你的代码尽可能简短。
  • 我们鼓励你包含上述要求以外的函数。即:我们鼓励你将你的解答分成若干函数,如果你想这样做的话(确实,有时这样做能够达成更短的解答)。当然,额外的函数同样计入你解答的总长度(他们的类型标识除外)。
  • 你最终应当提交一个名为Golf.hs的文件,其中定义的模块是Golf。所以文件首行应该是:

    module Golf where
  • 前三个最短的答案将赋予额外的2分,因此你最多可以获得4分。
  • 其他情况下长度不是那么重要,长但是正确的答案将获得对应的解答正确的分数。额外的分数取决于他们代码的风格。

提示

  • 尽可能多地使用标准库函数。这是这次作业的目的所在。例如使用map要比你自己造轮子方便得多。
  • 特别地,尝试使用标准库函数封装递归模式,而非你自己实现递归函数。
  • 或许你一开始不需要考虑长度问题,先让代码能够工作。之后再慢慢缩减长度。
  • 如果有其他不明白的事情,欢迎到Piazza上弄明白。

任务

练习 1 跳房子

你的第一个任务是写这样一个函数:

skips :: [a] -> [[a]]

这个函数输出一个列表的列表。第一个列表是和输入相同的。第二个列表包含输入的第2、4、6、8...个元素,第n个输出应该包含输入的第n、2n、3n...个元素。

例如:

skips "ABCD" == ["ABCD", "BD", "C", "D"]
skips "hello!" == ["hello!", "el!", "l!", "l", "o", "!"]
skips [1] == [[1]]
skips [True,False] == [[True,False], [False]]
skips [] == []

注意输出的列表数量和原输入列表的长度是一致的

我的解答
skips :: [a] -> [[a]]
skips xs = if length xs == 0 then [] else map (\n -> map snd $ filter (\(x,y) -> x `mod` n == 0) $ zip [1..length xs] xs) [1..length xs]

解释:这里利用了if-then-else语法糖省略了一个模式匹配。即上述函数声明等效如下:

skips :: [a] -> [[a]]
skips [] = []
skips xs = map (\n -> map snd $ filter (\(x,y) -> x `mod` n == 0) $ zip [1..length xs] xs) [1..length xs]

若输入为空列表,那么输出自然也是空列表。

若不为空,则首先从1开始为输入列表中的每个元素标上号(利用双元组和zip),对于输出的第i项,可以判断标号是否是i的倍数,是就留下,不是就扔掉(利用filter和匿名函数\(x,y) -> mod x n == 02)。而map函数则最终将上述产生每一项输出的函数作用到从1开始到length xs为止的列表的每一个元素上(相当于将每个元素作为参数传给函数,然后保持原有顺序将函数的输出保存为一个新列表)。最终得到的列表即为所求。

练习 2 极大值

极大值是一个数列中严格大于左右两个邻位的元素。例如[2,3,4,1,5]的唯一极大值是4,因为它比它左右两个邻居都大。而5因为右边没有元素,所以不是极大值。

写如下函数:

localMaxima :: [Integer] -> [Integer]

他的输出是输入数列的极大值列表。例如:

localMaxima [2,9,5,6,1] == [9,6]
localMaxima [2,3,4,1,5] == [4]
localMaxima [1,2,3,4,5] == []
我的解答
localMaxima :: [Integer] -> [Integer]
localMaxima xs = if length xs < 3 then [] else case xs of (x:y:z:xs) -> if x < y && y > z then y : localMaxima (y:z:xs) else localMaxima (y:z:xs) 

解读:这里的if语法糖和上面的效果一样,等效于:

localMaxima :: [Integer] -> [Integer]
localMAxima [] = []
localMAxima [a] = []
localMAxima [a,b] = []
localMaxima (x:y:z:xs) = if x < y && y > z then y : localMaxima (y:z:xs) else localMaxima (y:z:xs) 

即输入的数列长度小于等于2时,是没有极大值的,因此直接返回空列表。长度大于2时判断第二个元素是不是极大值。如果是就把当前元素留下,随后去掉第一个元素(相当于整个数列往前挪了一位)递归调用localMaxima;如果不是,那就去掉第一个元素直接递归调用。整体效果类似遍历输入的第2到n-1个元素是否为极大值,是则加入到输出列表。其中n为输入数组的元素个数。

练习 3 直方图

对于这个任务,写如下函数:

histogram :: [Integer] -> String

该函数接受一个由0到9(包含)组成的Integer类型的列表,并输出一个垂直的直方图来表示输入列表中每个数字的数量。你可以假设输入不会包含任何小于0或大于9的数字,但函数不应该受到不合规数字的影响。你的输出必须精确的符合下面的输出:

histogram [1,1,1,5] ==
 *
 *
 * *
==========
0123456789
histogram [1,4,5,4,6,6,3,4,2,4,9] ==
    *
    *
    * *
 ****** *
==========
0123456789

重要的提示:如果你在ghci中执行类似histogram [3,5]的命令,你应该见到如下输出:

"   * *    \n==========\n0123456789\n"

这个是函数返回值String的文本表示,其中包含的\n表示另起一行。为了真正的可视化这个函数的返回值,利用putStr函数:putStr (histogram [3,5])

我的解答
histogram :: [Integer] -> String
histogram xs = (helper $ map (\n -> fromIntegral $ length $ filter (==n) xs) [0..9]) ++ "==========\n0123456789\n" 
    where 
        helper ys = if foldl (+) 0 ys == 0 then [] else unlines $ (lines $ helper $ map (\x -> if x > 0 then (x-1) else 0) ys) ++ [line ys]
        line num = if length num == 0 then [] else case num of (z:zs) -> if z > 0 then "*" ++ line zs else " " ++ line zs

解读:显而易见,该函数的最后两行是固定的输出,因此直接放在最后和前面的图形连接起来(++ "==========\n0123456789\n" )。同样显而易见的是,不大可能不利用递归来完成这件事,而利用递归,也不大可能通过对自己的调用完成这件事(我认为即便能,也将十分复杂冗长)。因此我定义了两个额外函数。

首先是helper函数,他接受一个列表,这个列表的元素表明了对应角标的数字在原输入中有多少个。即判断原输入中等于0到9的元素个有多少个(map (\n -> fromIntegral $ length $ filter (==n) xs) [0..9]),其中fromIntegral是将lengthInt型返回值转换为Integer类型以交给helper处理;length $ filter (==n) xsfilter f list将函数f依次应用到list的元素上,若f返回值是True则该元素留下,否则弃之。(==n)相当于一个匿名函数,接收一个整数,判断是否等于n。最后由length求出留下列表的长度,这里就是对应数字的个数)。

helper函数接收到列表之后,首先判断这个列表是否所有数字都是0(这里利用foldl来实现,但理论上折叠方向无所谓,但是左折叠是惰性求值的,如果列表过长可能会占用过多的内存,但是考虑到这里就只是10个数字,惰性求值也无所谓的),如果是0则说明这个直方图处理完了,返回空列表。否则哪个数字不为0,本行对应的地方就应该有个星号(由函数line完成)。随后将包含个数的列表的非0项减一,表明已经处理了一行(由匿名函数\x -> if x > 0 then (x-1) else 0完成,判断给定x是否大于0,大于就减一,否则就返回0。再由map映射到列表的每一项,实现目的),最后将所有行组成一个列表,利用unlines函数将列表拼成一个字符串,列表的每一项由换行符\n分隔。

line函数接收包含个数的列表,空列表返回空列表,否则进行模式匹配取第一个元素,如果大于0就写个星号,否则写一个空格,再将余下的列表递归调用自己。效果是遍历包含个数的列表,如果对应项为0,就是空格,若不为0,就是星号。由此可产生一个从上到下从有星号到没星号的直方图。由于我们要的是星号在下面,因此组合每一行时要把顺序调整过来。即在helper函数中最后放本行的(在最下面),先处理个数减一的。由此递归产生的效果是由下至上从有星号到无星号。

我的结语

这次这个作业真的让我领略到了Haskell这门语言的简洁。也让我领略到了函数式编程的一大特色:

与指令式编程不同的是,你不要尝试教编译器如何做一个事,那样你会彻头彻尾的失败。你要做的是告诉编译器你要做什么事。用函数的语言描述你要做的事情,而不是像在C或Java里那样告诉程序怎么循环哪个数据要怎么变之类的细枝末节。只要你正确的描述了问题,那么问题就已经解决的一大半,剩下就是做什么的问题了。而一旦有了合适的函数,那么问题就轻而易举的解决了。

我觉得我或许在学习的过程中逐渐喜欢上了Haskell这门语言,以及相对的,不免觉得C或Java这些语言略微的有些繁琐(从上周的二叉树就能看出来,如果是C,那我得写死在电脑前)。或许这个是初学时的错觉,也或许是我还没深入到能够看清这种抽象结构第一这种机制的缺点所在。总而言之,我接下来会继续深入下去,能够接触到Haskell,不至于说不枉此生,但真的不白费这份折腾,非常值得。


  1. 代码高尔夫是指利用最简短的代码实现算法。
  2. 这里以中置函数调用普通函数的符号被markdown判定为行中代码,因此这里还原为了正常的函数调用形式。下同。

知识共享许可协议
【代码札记】The Day I Learned Haskell 4天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://www.skyblond.info/about.html 处获得。

Last Modified: December 15, 2018
Archives QR Code Tip
QR Code for this page
Tipping QR Code
0:00