寻求Haskell下简洁实现二维数组连通分量计数的方案

极简纯函数实现（约45token，满足O(mn)复杂度） #

直接基于坐标遍历+已访问集合追踪，避开重型图库的冗余转换：

import Data.Set (Set, empty, member, insert)
countIslands m=length$go empty[(i,j)|i<-[0..length m-1],j<-[0..length(head m)-1],m!!i!!j==1]where go _[]=[];go s((i,j):r)|(i,j)`member`s=go s r;otherwise=(i,j):go(foldr insert s neighbors)r where neighbors=[(i+1,j),(i-1,j),(i,j+1),(i,j-1)]>>=\(x,y)->if x>=0&&x<length m&&y>=0&&y<length(head m)&&m!!x!!y==1 then[(x,y)]else[]

• 核心逻辑：遍历所有1型坐标，未访问过则启动一次DFS标记所有连通节点，每启动一次计数+1
• 纯全函数：所有状态通过参数传递，无副作用
• 时间复杂度：每个坐标仅处理一次，Set操作的对数级开销不影响整体线性复杂度

二维数组适配图算法的标准方法 #

若必须使用图库（如algebraic-graphs），核心是精简坐标到节点的映射：

1. 将二维坐标(i,j)编码为整数i * n + j（n为矩阵列数）
2. 仅为值为1的坐标生成节点，为每个节点添加四方向相邻的1型节点作为边
3. 用dfsForest遍历，森林的数量即为岛屿数

简化版图库实现（约120token） #

import Algebra.Graph.AdjacencyMap(AdjacencyMap, empty, overlay, connect, dfsForest)
import Data.List(nub)
countIslands m=let n=length(head m);nodes=[i*n+j|i<-[0..length m-1],j<-[0..n-1],m!!i!!j==1];edges=[(u,v)|u<-nodes,let(i,j)=divMod u n,(x,y)<-[(i+1,j),(i-1,j),(i,j+1),(i,j-1)],let v=x*n+y,v`elem`nodes];graph=foldr(uncurry connect)empty edges in length$dfsForest graph nodes

注：此实现已砍掉冗余映射逻辑，但仍比直接递归遍历长，适合必须用图库的场景

内容的提问来源于stack exchange，提问作者Brendan Langfield