在 Haskell 中调试/可视化递归函数调用的最简单方法？

Question

我正在学习 Haskell，我决定实现这个简单的算法来完成插入排序算法的一部分：

while j > 0 and A[j-1] > A[j]
    swap A[j] and A[j-1]
    j ? j - 1
end while

我是这样的：

miniSort:: (Eq(a), Ord(a)) => Int -> [a] -> [a]
miniSort j list = if (list !! j) < (list !! (j-1)) && j >0
        then miniSort (j-1) (swapElements j (j-1) list) 
        else list

做对有点困难，但我做到了（我猜）。

在命令式编程语言中查看每一步我可以简单地做

while j > 0 and A[j-1] > A[j]
    print("j is $j")
    print("swapping $A[j] with $A[j-1]")
    swap A[j] and A[j-1]
    print("swapped list: $A")
    j ? j - 1
end while
print("ended with j $j")

在 Haskell 上，通过 Writer Monad 插入日志功能要困难得多。我什至没有尝试，因为它会一团糟，然后当我想清理日志记录时，它又会变得一团糟。

有没有办法查看 Haskell 中的函数调用分支？

例如：

miniSort 3 [1,2,4,3,7,8,5]

会扩展到这样的：

miniSort 3 [1,2,4,3,7,8,5] = if (3) < 4 && 3 >0
        then miniSort (2) [1,2,3,4,7,8,5]
miniSort 2 [1,2,3,4,7,8,5] = if (3) < 2 && 2 >0
        else [1,2,3,4,7,8,5]
[1,2,3,4,7,8,5]

Answer 1

正如 Fyodor Soikin 所说，trace将调试消息插入到任意代码中，当你应用它的语句被评估时，这些代码会被打印出来。

import Debug.Trace
import Text.Printf

miniSort j list
 = if trace (printf "miniSort %i %s = if %i < %i && %i>0"
                              j (show list) (list!!j) (list!!(j-1)) j)
                      $ list !! j < list !! (j-1) && j>0
    then trace (printf "then miniSort %i %s" (j-1) (show list))
           miniSort (j-1) (swapElements j (j-1) list) 
    else traceShowId list

但是，有几个警告：

• 如果你发现自己想要一个像 sort 这样的简单算法，那你就做错了。你确实是这样——在 Haskell 中对这样的列表进行排序是没有意义的。具体来说，对列表进行索引几乎从来都不是一个好主意：它笨拙、容易出错且速度缓慢。
  好的 Haskell 代码通常使用模式匹配而不是索引等。例如，

  type SortedList a = [a]
  
  insertion :: Ord a => a -> SortedList a -> SortedList a
  insertion n (x:xs)
   | n>x    = x : insertion n xs
  insertion n xs = n : xs
  
  insertSort :: Ord a => [a] -> SortedList a
  insertSort [] = []
  insertSort (x:xs) = insertion x $ insertSort xs
  

  看，任何地方都没有索引。更不可能在这里出错。
  （首先在 Haskell 列表上实现插入排序是否有意义当然是另一回事！）

• 因为（非 monadic）Haskell 并没有真正指定任何评估顺序，trace所以经常会出现意想不到的，可能是混乱的顺序。真的，只用它来调试一个大的、已经存在的函数中间的单个细节。一般来说，最好彻底重构和单元测试。
  而从未使用trace的实际记录！

• 使用 writer monad 不仅可以解决这些问题，还可以更容易（也更可靠）再次删除这些语句。一方面，您根本不需要这样做，因为您可以忽略日志数据，使用带有虚拟日志记录的多态 monad 将优化它而不是首先生成，等等。如果您这样做删除语句并取消编写类型，然后类型检查器将突出显示您忘记这样做的任何地方。