gpt4 book ai didi

list - Codetity与 `DList`和 `[]`之间的关系

转载 作者:行者123 更新时间:2023-12-01 22:32:12 26 4
gpt4 key购买 nike

我最近一直在尝试Codensity,它应该将DList[]关联起来。无论如何,我从来没有找到说明这种关系的代码。经过一些实验,我得出了以下结论:

{-# LANGUAGE RankNTypes #-}
module Codensity where

newtype Codensity f a = Codensity
{ runCodensity :: forall b. (a -> f b) -> f b }

type DList a = Codensity [] [a]

nil :: DList a
nil = Codensity ($ [])

infixr 5 `cons`
cons :: a -> DList a -> DList a
cons x (Codensity xs) = Codensity ($ (xs (x:)))

append :: DList a -> DList a -> DList a
append (Codensity xs) ys = Codensity ($ (xs (++ toList ys)))

toList :: DList a -> [a]
toList xs = runCodensity xs id

fromList :: [a] -> DList a
fromList xs = Codensity (\k -> k xs)

但是,在我的示例中, DList的定义有点棘手。有没有另一种方式陈述这种关系?这甚至是正确的方法吗?

最佳答案

有一种观点可能是DList是一种重新排序monoid操作的方法,就像Codensity是一种重新排序monad操作的方法一样。
[]a上的免费monoid,所以让我们使用免费的作家monad来表示列表,即Free ((,) a):

module Codensity where

import Control.Monad
import Control.Monad.Free
import Control.Monad.Codensity
import Control.Monad.Trans (lift)

type DList a = Free ((,) a) ()

现在我们可以定义标准列表操作:
nil :: DList a
nil = return ()

singleton :: a -> DList a
singleton x = liftF (x, ())

append :: DList a -> DList a -> DList a
append = (>>)

infixr 5 `snoc`
snoc :: DList a -> a -> DList a
snoc xs x = xs >> singleton x

exec :: Free ((,) a) () -> [a]
exec (Free (x, xs)) = x : exec xs
exec (Pure _) = []

fromList :: [a] -> DList a
fromList = mapM_ singleton

toList :: DList a -> [a]
toList = exec

对于 snoc,此表示形式与list具有相同的缺点。我们可以验证
last . toList . foldl snoc nil $ [1..10000]

需要大量(二次)时间。但是,就像每个免费的monad一样,可以使用 Codensity对其进行改进。我们只是将定义替换为
type DList a = Codensity (Free ((,) a)) ()

toList
toList = exec . lowerCodensity

现在,相同的表达式将立即执行,因为 Codensity对操作进行了重新排序,就像原始差异列表一样。

关于list - Codetity与 `DList`和 `[]`之间的关系,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32191851/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com