duangsuse::Echo

实在是没有那个力气开几个理论向学习，因为定理证明、PL 理论那些已经够累了... 代数程序逻辑依然在学，反正理论向都是均衡发展但都很薄弱就是了现在具体来讲就是 The Little Schemer 终于熟悉了一点这个列表处理语言... 不过我觉得还是 Haskell 好，因为 Haskell 更符合直觉（看很多用 Haskell 讲程序分析的论文就知道），Scheme 一类的一大堆 car cdr 让不让人活了具体就是（拿 foldr 和 foldl 举个例子） Haskell 里（比较简单比较…

如果觉得这个例子不好的话，刚才看这篇博文（教你们拿 Racket，一个 Scheme 实现写基于 Lambda Calculus 的解释器的）的时候突然发现这个例子非常不错（实际上，很多 #Haskell 入门教程都会拿这个做例子）

(define tree-sum
  (lambda (exp)
    (match exp                         ; 对输入exp进行模式匹配
      [(? number? x) x]                ; exp是一个数x吗？如果是，那么返回这个数x
      [`(,e1 ,e2)                      ; exp是一个含有两棵子树的中间节点吗？
       (let ([v1 (tree-sum e1)]        ; 递归调用tree-sum自己，对左子树e1求值
             [v2 (tree-sum e2)])       ; 递归调用tree-sum自己，对右子树e2求值
         (+ v1 v2))])))                ; 返回左右子树结果v1和v2的和

(tree-sum '(1 2))
;; => 3
(tree-sum '(1 (2 3)))
;; => 6
(tree-sum '((1 2) 3))
;; => 6

如果用 Haskell 写几乎一样的程序呢？

首先我们的 Haskell 的确是静态强类型（statically strong typed, type inference supported）的语言，所以类似 Scheme 那样直接拿链表抽象一切就免了（

data BinaryTree a = Leaf a | PrimNode a a | CompNode (BinaryTree a) (BinaryTree a)
t1 = PrimNode 1 2
t2 = CompNode (Leaf 1) (PrimNode 2 3)
t3 = CompNode (PrimNode 1 2) (Leaf 3)
t4 = CompNode (PrimNode 1 2) (PrimNode 3 4)

treeSum :: BinaryTree Int -> Int
treeSum (Leaf n) = n
treeSum (PrimNode a b) = a + b
treeSum (CompNode l r) = treeSum l + treeSum r

main 
  = (foldl f v) $ (println . treeSum) <$> [t1, t2, t3, t4]
    where      
      println x = print x               
      f = (>>)
      v = putStr ""

（为了方便起见，大家可以看到 Haskell 的版本里那个 data 其实不是『等价』Racket 里我们所预期的表结构的）

当然，如果我们写『完全等价』的呢？

t1 = [1, 2]
t2 = [1, [2, 3]]
t3 = [[1, 2], 3]
t4 = [[1, 2], [3, 4]]

treeSum' :: [Int] -> Int
然后就写不出等价的来...

<del>
treeSum' :: [Int] -> Int
treeSum' xs
| length xs == 1 = head xs
| (x : xs) = x + treeSum' xs
| otherwise = treeSum' (head xs) + treeSum' (head (tail xs))

因为这个逻辑实在有点复杂，貌似简单一点的 Haskell Cons 模式匹配弄不了，只好使用 Guard Pattern（
</del>

『好的程序应该反映出它所处理的数据结构』
这话不是我说的，看完上面的小学生水平 Haskell/Racket 代码后，大家应该理解了这句话吧。

如果有喜欢 #Scheme 的同学，必须记得看完 The Little Schemer（轮子哥管它叫『儿童书』）先再出去『吓人』（悄悄告诉你们... 我就是还没看完所以连 #FP 的 QQ 群都不敢进... hhhh 🤔

33 viewsduangsuse ¯\_(ツ)_/¯ |学渣 ∈ [E²PROM, 含幺半群), edited 16:02