'DList'和'[]`与Codensity的关系 [英] Relation between `DList` and `[]` with Codensity

问题描述

我最近一直在试验 Codensity ，它应该将 DList 与 [] 等等。无论如何，我从来没有找到说明这种关系的代码。

I've been experimenting with Codensity lately which is supposed to relate DList with [] among other things. Anyway, I've never found code that states this relation. After some experiments I ended up with this:

{-# 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 的定义感觉有点。有没有不同的方式来陈述这种关系？这是甚至正确的方法吗？

However, the definition of DList feels a bit icky in my example. Is there a different way to state this relation? Is this even the right way to do this?

推荐答案

一个视图可能是 DList 是对monoid操作进行重新排序的一种方式，就像 Codensity 是对monad操作进行重新排序的方式一样。

One view could be that DList is a way for reordering monoid operations, just as Codensity is a way for reordering monad operations.

[] 是 a 上的一个自由单子，所以让我们使用免费的作家monad来表示列表，即 Free（（，）a）：

[] is a free monoid on a, so let's represent lists using a free writer monad, that is 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) ()

现在我们可以定义标准列表操作：

Now we can define the standard list operations:

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 。我们可以验证

This representation has the same drawbacks as list when it comes to snoc. We can verify that

last . toList . foldl snoc nil $ [1..10000]

需要大量（二次）时间。但是，就像每个免费的monad一样，可以使用 Codensity 来改进。我们只是用

takes a significant (quadratic) amount of time. However, just as every free monad, it can be improved using Codensity. We just replace the definition with

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

和 toList with

and toList with

toList = exec . lowerCodensity

现在相同的表达式立即执行，如 Codensity 重新排序操作，就像原始差异列表一样。

Now the same expression is executed instantly, as Codensity reorders the operations, just like the original difference lists.

这篇关于'DList'和'[]`与Codensity的关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！