内容简介：函数式 dfs （深度优先搜索）
这篇博客主要说说我很早以前整出来的函数式 dfs ，老早就想写博客了但是现在才有空。本文应该是很简单的，因为我会先说一些预备知识，说不定你看完还能懂点 Haskell ，多好。
消除恐惧
你需要消除你对那些概念的恐惧，而且就我个人来说，我觉得理解 Monad 是自函子范畴上的幺半群
和 在实际编程中使用 >>=
是没有关系的。
所以我觉得，就算你只学过 Java ，也是可以看这篇文章的（不过你还需要消除对于 新语言
的恐惧）。
为什么我要说这个呢？因为我最早也是很恐惧 Haskell 这类语言的，但后来发现这些东西还是蛮好玩的。
虽然和编译器硬肛不是什么好受的事情，不过以前的 debug 经历也很不好受啊，而使用 Haskell 这种
It compiles, it probably works
的语言，可能对你来说是一个好的新的尝试也说不定（？）。
预备知识
符号约定
定义符号
(a -> b)
为类似这样的东西：参数类型为 a 返回类型为 b 的函数。
定义符号
(a -> b -> c)
为类似这样的东西：参数 2 个，类型为 a 和 b ，返回类型为 c 的函数。（其实这是柯理化过的，但是
本文不会讲）
定义符号
fun :: a -> b
为类似这样的东西：函数 fun 接收一个 a 类型的参数，返回一个 b 类型的值。
定义符号
fun :: Functor f => f a -> f b
为类似这样的东西：函数 fun 接收一个 f a 类型的参数，返回一个 f b 类型的值。其中， f 是一个 Functor 。
我保证
你不会看到关于任何 如何定义一个 Functor
如何定义一个 Monad
为什么 List 是一个 Functor
之类的东西。
Functor
这里可以理解为
可以进行 map
操作的东西
。在我的印象中， Java 等语言中一般都只有 List
等东西才有 map
， 而这里的 map
是广义的，即：
map :: Functor f => (a -> b) -> f a -> f b
这个是什么意思呢？举个例子，比如对于 List
，它是一个 Functor
，然后我们可以通过 map
把一个 List<a>
变成一个 List<b>
—— 不过你还需要一个函数 a -> b
。
也就是说，我们有：
map :: (a -> b) -> List a -> List b
这样看是不是好理解多了？我们接收一个 (a -> b)
的函数和一个 List<a>
，返回一个 List<b>
。
那么同理，把 List
抽象为一个 Functor
就可以得到最开始我给出的定义了：
map :: Functor f => (a -> b) -> f a -> f b
我们再来想想 Kotlin 的 Nullable
类型（看懂下文不需要学 Kotlin 因为下一句就解释了这是什么意思）。 一个 Nullable
有两种可能的值，也就是 null
和 正常的值。
那么，我们可以有这样一个操作：
map :: (a -> b) -> Nullable a -> Nullable b
对一个 Nullable
进行 map
，如果它是正常值，就返回这个值传给第一个参数（那个函数）后的返回的结果。
如果它是 null
，那就继续返回 null
。
因此， Nullable 和 List 都是 Functor。
在 Haskell 中，我们可以把它简写为 <$>
。也就是
map toInt [1.1, 2.1, 3.1] -- 等价于 toInt <$> [1.1, 2.1, 3.1]
当然这里的等价是忽略了运算符优先级的。可能两者在换来换去的时候需要加括号。
顺带一提， Nullable
在 Haskell
里面的等价物是 Maybe
，有值的叫 Some
， null
对应的是 Nothing
。
Alternative
这是另一个奇特的东西，它理解起来更简单。举个例子，我现在有五个 Nullable
。我要对他们挨个遍历找出第一个非 null
的。
那么 Nullable
作为一个 Alternative
就可以这样操作（这是很早以前就有的操作了）
a = getNullable b = getNullable c = getNullable d = getNullable e = getNullable firstNotNull = a <|> b <|> c <|> d <|> e
看是不是很清晰 QAQ
最后一行这个表达式相当于是把一堆 Alternative
穿起来了，它最后的值也是 Alternative
（因为如果全部都是 null
那最后也只能是 null
）。
要使用 Alternative
，请加上这个：
import Control.Applicative
dfs
那么，我们可以根据 dfs
的思路来把这两个函数式编程的概念融入这个算法中。
如果你不知道什么是 dfs
那就太惨啦。这里说的是一个很狭义的 dfs
（就是走迷宫，初等 OI 内容，我校初中生每个都会做）， C++ 版本可以参考这些题目以及相关参考题解（因为这些代码都是我很早很早很早的时候写的了）：
- openjudge 1818 以及 我的题解 （不过这个似乎是 bfs 解）
- openjudge 1792 以及 我的题解 （不过这个似乎是 bfs 解）
找了半天没找到 dfs 的。。。呃。。。我上个专门讲的：
题目
这还是一道 <4kyu> 的题目，先上原题：
语言支持 Haskell
JavaScript
Python
Ruby
。
我们选 Haskell 。
可以看到数据模型：
type XY = (Int, Int) data Move = U | D | R | L deriving (Eq, Show)
关于题面，英文的就自己看了，这是我稍微改了下的谷歌翻译版本：
一个可怜的矿工被困在一个矿井里，你必须帮助他离开！ 只不过这个矿是黑暗的，所以你必须告诉他去哪里。 在这个 kata 中，您将必须实现一个解决方法（map，miner，exit），该方法必须返回矿工必须采取的路径才能到达出口， 例如：['up'，'down' ， '右左']。有4个可能的动作，向上，向下，向左，向右，没有对角线这种操作。 map是布尔值的二维数组，表示正方形。False 代表墙壁，True 代表可以走的路（矿工可以走）。它永远不会大于 5 x 5。 它被列为一列列。所有列将始终是相同的大小，尽管不一定与行大小相同（换句话说，地图是矩形，不一定是正方形）。 地图永远不会包含任何环，所以总是只有一个可能的路径。地图可能包含死胡同。 miner 是起始矿工的位置，作为由两个自然数值 x 和 y 组成的对象。例如 (0, 0) 将是左上角。 exit 是出口的位置，与矿工的格式相同。 请注意，矿工不能走出地图，因为它是隧道。 举例：
下面是例子：
let map = [[True, False],
[True, True]]
solve map (0,0) (1,1)
-- Should return [R, D]
思路
首先， dfs 到某一个点时的决策，有以下几个因素。
- 这个点是否是目标点（如果是，就表示成功了）
- 这个点是否已经被走过（判重）
- 这个点能不能走（有些地方是不能走的，所以才叫迷宫啊）
- 这个点是否超出迷宫范围（不能走出去了）
上面是几个特殊情况（会导致 dfs
递归函数直接返回），剩下的时候，对周围四个点分别进行递归调用。
由于这道题要求我们记录路径，因此还得把路径存在参数里面。
总体来说，考虑到：
- 起点终点 +2
- 地图 +1
- 走过的点 +1
- 目前的路线 +1
总共需要五个参数。
那么 dfs 函数原型就出来了：
dfs :: [[Bool]] -> [XY] -> XY -> XY -> Maybe [Move] dfs m v s e = undefined
这里体现出了刚才的思想——返回的是一个 Maybe
，因此我们可以对它进行 <$>
和 <|>
。
然后实现那些返回的条件以及搜索的过程就好了。举个例子，判断目标：
dfs m v s e |s == e = Just []
判重：
dfs m v s e |elem s v = Nothing
其中， v
是判重用的序列。
剩下的请读者自己思考哦。
以及最后的对四个边的遍历，我这里就写两条边吧：
dfs m v s e
|otherwise = ((R :) <$> dfs m (s : v) (x + 1, y) e)
<|> ((D :) <$> dfs m (s : v) (x, y + 1) e)
看到了吗，这里就体现出了对 Functor
和 Alternative
的使用。
首先，把当前行走的方向加进“路径”中，然后递归，看是否走得通。要是走通了，就把剩下的路径加上这一步的路径。
等成功后回溯到开头，就可以把这整条路径从末尾给“收”起来（回溯）。
部分概念在 Kotlin 中的等价物
| Haskell | 举例 | Kotlin | 举例 |
|---|---|---|---|
<$>
|
func <$> value
|
?.run
|
value?.run(func)
|
<|>
|
val1 <|> val2
|
?:
|
val1 ?: val2
|
所以说 Kotlin 还是很函数式的（逃
最终的代码
为了防止你们直接复制过去提交破坏游戏规则，我不直接给（傲娇
这里贴个链接，根据我的推断，应该是必须提交并通过该题才能看到这个链接的内容的：
各位大佬可以过来给个 best practise 或者 clever 啥的（逃
毕竟比题解区那些辣鸡超长的代码不知道高到哪里去了。
作业
如果读者想检验自己是否真的看懂了本文，试试这道题，支持 Haskell
JavaScript
。
反正都是 <4kyu> 的大水题（逃
更新
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 深度学习常用损失函数总览：基本形式、原理、特点
- 深度人脸识别中不同损失函数的性能对比
- JS中解决JSON中函数及对象的深度拷贝
- 深度学习的数学原理-复杂函数求导的链式传递及多变量近似公式
- Python 拓展之特殊函数（lambda 函数，map 函数，filter 函数，reduce 函数）
- Python 函数调用&定义函数&函数参数
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
