2

函数式程序效率低下的一个典型案例是reverse从规范编写的函数

import Prelude()

[] ++ ys = ys
(x:xs) ++ ys = x:(xs ++ ys)

reverse []     = []
reverse (x:xs) = (reverse xs) ++ [x]

使用关联性，可以得出一个有效的反向

-------- REWRITE ------

-- RULE : ++ relation (deduced)
-- reverse xs = reverse xs ++ []

-- RULE : [] relation -- case split
-- reverse []      = reverse [] ++ []
-- reverse (x::xs) = reverse (x::xs) ++ [] 

-- RULE : reverse relation 
-- reverse []      = []                
-- reverse (x::xs) = (reverse xs ++ [x]) ++ []

-- RULE : ++ relation (deduced)
-- reverse []      = []                
-- reverse (x::xs) = reverse xs ++ ([x] ++ [])

-- RULE : ++ relation
-- reverse []      = []                
-- reverse (x::xs) = reverse xs ++ (x::[])

-- RULE :  (language)
-- reverse' []      _   = []                
-- reverse' (x::xs) acc = reverse xs ++ acc
-- reverse  xs = reverse' xs []

reverse_eff xs = reverse' xs []
  where 
    reverse' [] ys  = ys
    reverse' (x:xs) ys  = reverse' xs (x:ys)

但是，问题首先来自哪里？

  • 我们指示特定的订单++
  • 由我们的语言定义的组合定义了我们的组合的顺序++
  • 我们的语言不知道法律，源于代码本身，也不知道效率的概念。

我们真正想做的是：

  • 指定一个（函数）关系++，由它的所有定律正确商化
  • 为它使用关系组合，它隐藏了将使用哪个特定的括号
  • 在使用站点，选择一个最适合我们的访问模式和目标的括号（在 的情况下reverse，这意味着移动所有括号以匹配结果列表的构造方式）

是否有任何语言可以产生一些规律，并根据一些指标寻找最好的重写？

4

0 回答 0