最左边-最里面和最外面(Haskell)

Question

我不太了解此函数中 Haskell 的 Reduction:

removeone :: Eq a = > a -> [ a ] -> [ a ]
removeone _ [] = [] 
removeone x ( y : ys ) 
   | x == y  =  removeone x ys
   | otherwise =  y : ( removeone x ys )

remdups :: Eq a = > [ a ] -> [ a ]
remdups [] = []
remdups ( x : xs ) = x : remdups ( removeone x xs )

如何使用此函数来解释列表中的归约步骤（例如 remdups [3,7,3,7,5,7]）？

Answer 1

从 remdups [3,7,3,7,5,7] 开始，尽可能简化左侧的表达式。请记住，[x,y,z] 是 x:y:z:[] 的 shorthand。因此 remdups (3:7:....) = 3 : remdups (removeone 3 (7:....)) = ... 现在你需要使用 removeone 的定义，因为没有 remdups 的等式适用。 removeone 生成 : 或 [] 后，您将 return 简化 remdups 调用。

一行减一。注释中是带有减少代码的行号。我的示例使用 Outermost（惰性）缩减。

remdups [3,7,3,7,5,7]
3:remdups (removeone 3 [7,3,7,5,7]) -- 9
3:remdups (7:(removeone 3 [3,7,5,7])) -- 5
3:7:remdups (removeone 7 (removeone 3 [3,7,5,7])) -- 9
3:7:remdups (removeone 7 (removeone 3 [7,5,7])) -- 4
3:7:remdups (removeone 7 (7:(removeone 3 [5,7]))) -- 5
3:7:remdups (removeone 7 (removeone 3 [5,7])) -- 4
3:7:remdups (removeone 7 (5:(removeone 3 [7]))) -- 5
3:7:remdups (5:(removeone 7 (removeone 3 [7]))) -- 5
3:7:5:remdups (removeone 5 (removeone 7 (removeone 3 [7]))) -- 9
3:7:5:remdups (removeone 5 (removeone 7 (7:(removeone 3 [])))) -- 5
3:7:5:remdups (removeone 5 (removeone 7 (removeone 3 []))) -- 4
3:7:5:remdups (removeone 5 (removeone 7 [])) -- 2
3:7:5:remdups (removeone 5 []) -- 2
3:7:5:remdups [] -- 2
3:7:5:[] -- 8

为了完整起见，还有其他减少程序。例如最左最内（贪婪）减少。在这个示例中是相同的结果，但是例如 head $ remdups [1..] 贪婪减少会 'hang'。所以据我所知，最左边-最里面仅在理论上使用或用于内存优化：

remdups [3,7,3,7,5,7]
3:remdups (removeone 3 [7,3,7,5,7])
3:remdups (7:(removeone 3 [3,7,5,7]))
3:remdups (7:(removeone 3 [7,5,7]))
3:remdups (7:(7:(removeone 3 [5,7])))
3:remdups (7:(7:(5:(removeone 3 [7]))))
3:remdups (7:(7:(5:(7:(removeone 3 [])))))
3:remdups (7:(7:(5:(7:([])))))
3:remdups [7,7,5,7] -- shorthand
3:7:remdups (removeone 7 [7,5,7])
3:7:remdups (removeone 7 [5,7])
3:7:remdups (5:(removeone 7 [7]))
3:7:remdups (5:(removeone 7 []))
3:7:remdups (5:([]))
3:7:remdups [5] -- shorthand
3:7:5:remdups (removeone 5 [])
3:7:5:remdups ([])
3:7:5:remdups [] -- shorthand
3:7:5:[]
[3,7,5] -- shorthand

Answer 2

在伪代码中，我们有

rem1 x (x:t)  =   rem1 x t
rem1 x (a:t)  = a:rem1 x t                    ;  rem1 x [] = []

remdups (a:t) = a:remdups (rem1 a t)          ;  remdups [] = []

Innermost-Leftmost（急切评价）：

remdups               [3,7,3,7,5,7]
= 3:  remdups   (rem1 3 [7,3,7,5,7])
= 3:  remdups   (7:rem1 3 [3,7,5,7])
= 3:  remdups   (7:  rem1 3 [7,5,7])
= 3:  remdups   (7:7:  rem1 3 [5,7])
= 3:  remdups   (7:7:5:  rem1 3 [7])
= 3:  remdups   (7:7:5:7: rem1 3 [])
= 3:  remdups   (7:7:5:7: []       )
= 3: 7:  remdups  (rem1 7 (7:5:7:[]))
= 3: 7:  remdups  (  rem1 7 (5:7:[]))
= 3: 7:  remdups  (  5:rem1 7 (7:[]))
= 3: 7:  remdups  (  5:  rem1 7 ([]))
= 3: 7:  remdups  (  5:  []         )
= 3: 7: 5:  remdups  (rem1 5     [] )
= 3: 7: 5:  remdups  []
= 3: 7: 5: []       -- 15 reductions

最外层（Haskell 在做什么）：

remdups                               [3,7,3,7,5,7]
= 3:                   remdups  (rem1 3 [7,3,7,5,7])
= 3:                   remdups  (7:rem1 3 [3,7,5,7])
= 3: 7:          remdups  (rem1 7 (rem1 3 [3,7,5,7]))
= 3: 7:          remdups  (rem1 7 (  rem1 3 [7,5,7]))
= 3: 7:          remdups  (rem1 7 (7:  rem1 3 [5,7]))
= 3: 7:          remdups  (rem1 7 (    rem1 3 [5,7]))
= 3: 7:          remdups  (rem1 7 (   5: rem1 3 [7]))
= 3: 7:          remdups  (5:rem1 7 (    rem1 3 [7]))
= 3: 7: 5: remdups  (rem1 5 (rem1 7 (    rem1 3 [7])))
= 3: 7: 5: remdups  (rem1 5 (rem1 7 ( 7: rem1 3  [])))
= 3: 7: 5: remdups  (rem1 5 (rem1 7 (    rem1 3  [])))
= 3: 7: 5: remdups  (rem1 5 (rem1 7      []         ))
= 3: 7: 5: remdups  (rem1 5 []                       )
= 3: 7: 5: remdups  []   
= 3: 7: 5: []       -- 15 reductions

最左边-最里面和最外面(Haskell)

Leftmost-Innermost and Outermost(Haskell)

haskell

function

list

reduction