我正在寻找一个库,可以计算一组可变参数运算符下的固定点/闭包。例如,
fixwith [(+)] [1]
对于整数,应该计算所有自然数N(1..
)。我尝试着写了一下,但有些地方还不够。它不是很高效,并且我觉得我的多元函数处理方式不是最优雅的。此外,是否可能使用内置的fix
函数而不是手动递归来编写?
class OperatorN α β | β -> α where
wrap_op :: β -> (Int, [α] -> α)
instance OperatorN α (() -> α) where
wrap_op f = (0, \[] -> f ())
instance OperatorN α (α -> α) where
wrap_op f = (1, \[x] -> f x)
instance OperatorN α ((α, α) -> α) where
wrap_op f = (2, \[x, y] -> f (x, y))
instance OperatorN α ((α, α, α) -> α) where
wrap_op f = (3, \[x, y, z] -> f (x, y, z))
instance OperatorN α ((α, α, α, α) -> α) where
wrap_op f = (4, \[x, y, z, w] -> f (x, y, z, w))
type WrappedOp α = (Int, [α] -> α)
fixwith_next :: Eq α => [WrappedOp α] -> [α] -> [α]
fixwith_next ops s = List.nub (foldl (++) s (map g ops)) where
g (0, f) = [f []]
g (arity, f) = do
x <- s
let fx = \xs -> f (x:xs)
g (arity - 1, fx)
fixwith ops s
| next <- fixwith_next ops s
, next /= s
= fixwith ops next
fixwith _ s = s
示例,
> fixwith [wrap_op $ uncurry (*)] [-1 :: Int]
[-1,1]
> fixwith [wrap_op $ uncurry (*)] [1 :: Int]
[1]
> fixwith [wrap_op $ max 3, wrap_op $ \() -> 0] [1 :: Int]
[1,3,0]
设置版本
这并不会显著提高性能,尽管我想我只需要找出如何减少计算量才能使其更快。
import qualified Control.RMonad as RMonad
class OperatorN α β | β -> α where
wrap_op :: β -> (Int, [α] -> α)
instance OperatorN α (() -> α) where
wrap_op f = (0, \[] -> f ())
instance OperatorN α (α -> α) where
wrap_op f = (1, \[x] -> f x)
instance OperatorN α ((α, α) -> α) where
wrap_op f = (2, \[x, y] -> f (x, y))
instance OperatorN α ((α, α, α) -> α) where
wrap_op f = (3, \[x, y, z] -> f (x, y, z))
instance OperatorN α ((α, α, α, α) -> α) where
wrap_op f = (4, \[x, y, z, w] -> f (x, y, z, w))
type WrappedOp α = (Int, [α] -> α)
fixwith_next :: Ord α => [WrappedOp α] -> Set α -> Set α
fixwith_next ops s = Set.unions $ s : map g ops where
g (0, f) = RMonad.return $ f []
g (arity, f) = s RMonad.>>= \x ->
g (arity - 1, \xs -> f (x:xs))
fixwith' ops s
| next <- fixwith_next ops s
, next /= s
= fixwith' ops next
fixwith' _ s = s
fixwith ops s = Set.toList $ fixwith' ops (Set.fromList s)
设置懒惰版本
我使用了 RMonad
来简化代码,并像Daniel建议的那样将其设置为懒惰版本。不幸的是,我认为大部分时间都花在了实际的乘法例程上,所以我没有看到这个改变带来的性能提升。但是懒惰版本很酷。
notin :: Ord α => Set α -> Set α -> Set α
notin = flip Set.difference
class Ord α => OperatorN α β | β -> α where
next_values :: β -> Set α -> Set α
instance Ord α => OperatorN α (α -> α) where
next_values f s = notin s $ s RMonad.>>= \x -> RMonad.return (f x)
instance Ord α => OperatorN α (α -> α -> α) where
next_values f s = s RMonad.>>= \x -> next_values (f x) s
instance Ord α => OperatorN α (α -> α -> α -> α) where
next_values f s = s RMonad.>>= \x -> next_values (f x) s
instance Ord α => OperatorN α (α -> α -> α -> α -> α) where
next_values f s = s RMonad.>>= \x -> next_values (f x) s
-- bind lambdas with next_values
fixwith_next :: Ord α => [Set α -> Set α] -> Set α -> Set α
fixwith_next nv_bnd s = Set.unions $ map (\f -> f s) nv_bnd -- bound next values
fixwith' :: Ord α => [Set α -> Set α] -> Set α -> [α]
fixwith' ops s@(fixwith_next ops -> next)
| Set.size next == 0 = []
| otherwise = (Set.toList next) ++ fixwith' ops (Set.union s next)
fixwith ops s = (Set.toList s) ++ fixwith' ops s
fixwith_lst ops = fixwith ops . Set.fromList
示例
> take 3 $ fixwith [next_values (+2)] (Set.fromList [1])
[1,3,5]
我必须放弃一元操作,但这并不是致命的问题。
take 2 $ fix (\x -> List.nub $ [1, 2] ++ x)
。 - gatoatigradofix
,但这不会是一个_有趣的_使用fix
。在Haskell中,fix
等同于递归--你可以通过调用fix
使任何递归定义变为非递归定义,并且你可以将任何对fix
的调用替换为递归定义。因此,“我能在定义这个特定函数时使用fix
吗?”这个问题等同于“我能在定义这个特定函数时使用递归吗?”答案是肯定的,但这个问题是愚蠢的,因为_编写函数_才是真正的目标,无论你是否使用递归都是次要的。 - Daniel Wagner