简化haskell功能

Question

我真的在与Haskell atm挣扎.

我花了将近6个小时编写了一个能够满足我想要的功能.不幸的是我对它的外观并不满意.

有人可以给我任何提示如何重写它吗？

get_connected_area :: Eq generic_type => [[generic_type]] -> (Int, Int) -> [(Int,Int)] -> generic_type -> [(Int,Int)]
get_connected_area habitat point area nullValue
  | elem point area = area
  | not ((fst point) >= 0) = area
  | not ((snd point) >= 0) = area
  | not ((fst point) < (length habitat)) = area
  | not ((snd point) < (length (habitat!!0))) = area
  | (((habitat!!(fst point))!!(snd point))) == nullValue = area
  | otherwise = 
    let new_area = point : area
    in 
    get_connected_area habitat (fst point+1, snd point) (
        get_connected_area habitat (fst point-1, snd point) (
            get_connected_area habitat (fst point, snd point+1) (
                get_connected_area habitat (fst point, snd point-1) new_area nullValue
                ) nullValue
            ) nullValue
    ) nullValue

函数get是[[generic_type]](表示横向映射)并搜索不等于给定nullValue的点周围的完全连接区域.

例如.:

如果函数被调用如下:

get_connected_area [[0,1,0],[1,1,1],[0,1,0],[1,0,0]] (1,1) [] 0

字面意思是

0 1 0
1 1 1
0 1 0
1 0 0

表示地图(如谷歌地图).从点(坐标)(1,1)开始我想得到与给定点形成连通区域的元素的所有坐标.

因此结果应该是:

0 1 0
1 1 1
0 1 0
1 0 0

和相应的返回值(粗体1的坐标列表):

[(2,1),(0,1),(1,2),(1,0),(1,1)]

Answer 1

一个小的变化是你可以使用模式匹配变量point.这意味着您可以使用(x, y)而不是point在函数声明中:

get_connected_area habitat (x, y) area nullValue = ...

现在,无论你有fst point,只是把x,到处你snd point,放y.

另一种修改是为子表达式使用更多变量.这可以帮助嵌套递归调用.例如,为最内层嵌套的调用创建一个变量:

....
where foo = get_connected_area habitat (x, y-1) new_area nullValue

现在只是把foo而不是电话.现在可以针对"新"最内层呼叫重复此技术.(请注意,您应该选择一个比描述更具描述性的名称foo.也许down？)

注意与之not (x >= y)相同x < y.使用它来简化所有条件.由于这些条件测试点是否边界矩形内,最这个逻辑可以被分解到功能isIn :: (Int, Int) -> (Int, Int) -> (Int, Int) -> Bool这将使get_connected_area更具有可读性.

Answer 2

这将是我第一次快速浏览函数,以及可能通过代码审查的最小值(仅限于样式):

getConnectedArea :: Eq a => [[a]] -> a -> (Int, Int) -> [(Int,Int)] -> [(Int,Int)]
getConnectedArea habitat nullValue = go where
  go point@(x,y) area
      | elem point area = area
      | x < 0 = area
      | y < 0 = area
      | x >= length habitat = area
      | y >= length (habitat!!0) = area
      | ((habitat!!x)!!y) == nullValue = area
      | otherwise = 
          foldr go (point : area) 
            [ (x+1, y), (x-1, y), (x, y+1), (x, y-1) ]

我们绑定habitat并且nullValue一次处于顶层(澄清递归工作正在做什么),删除谓词中的间接,使用camel-case(在函数应用程序发生的地方隐藏),替换generic_type为a(在这里使用噪声变量实际上是相反的从你想要的那个开始的效果;我最终试图找出你想要调用的特殊语义,当有趣的是类型无关紧要时(只要它可以比较相等)).

在这一点上,我们可以做很多事情:

• 假装我们正在编写真正的代码并担心将列表视为数组(!!,和length)和sets(elem)的渐近,并使用正确的数组和设置数据结构
• 将边界检查(以及可能的空值检查)移动到新的查找函数中(目标是尽可能只有一个... = area子句)
• 考虑对算法的改进:我们可以避免递归地检查我们刚从算法中得到的单元格吗？我们可以避免area完全通过(使我们的搜索很好地懒惰/"生产")？