Haskell 双链表函子

Question

我最近为 DoubeList（双向链表）数据类型的以下定义创建了一个 Functor 的实例。 (Motivated by this post) 我的目标是定义 Functor 的一个实例，以便 fmap f db 中的函数 f 应用于双向链表中每个节点的第一个字段 - 无论哪个值构造函数传递给 fmap。之后，我无法向自己解释我的 fmap 定义实际上是如何计算的。

例如，传递一些由 LeftEnd 构造的值将导致 Middle 或 RightEnd 上的 fmap。同样，Middle 或 RightEnd 构造函数对某些值的 fmap 将导致前一个或下一个节点上的 fmap - 依此类推。

然而，在使用 returnFirst 和 returnNext 探索 LeftEnd、MiddleEnd 或 RightEnd 上的 fmapping 结果后，似乎对于某些函数fmap f db 中的 f，f 仅应用于每个节点中的第一个字段一次 - 就像我打算做的那样。但我似乎无法理解这是怎么可能的。

我的直觉告诉我 Haskell 的惰性正在发挥作用。任何见解或解释将不胜感激！

module DoubleList where

    data DoubleList a
        = LeftEnd  a (DoubleList a)
        | Middle   a (DoubleList a) (DoubleList a)
        | RightEnd a (DoubleList a)

    -- perserve identity
    -- fmap id create = id create
    -- perserve function composition
    -- fmap (f . g) create = fmap f . fmap g $ create
    instance Functor DoubleList where
        fmap f (LeftEnd a nxt) = LeftEnd (f a) (fmap f nxt)
        fmap f (Middle a prev nxt) = Middle (f a) (fmap f prev) (fmap f nxt)
        fmap f (RightEnd a prev) = RightEnd (f a) (fmap f prev)
    
    instance Show a =>  Show (DoubleList a) where 
        show (LeftEnd x next) = "Left End " ++ show x ++ "<->" ++ show next
        show (Middle x prev next) = show x ++ "<->" ++ show next
        show (RightEnd x next) = show x  ++ " Right End"
    
    create :: DoubleList Integer
    create = let n1 = LeftEnd  1 n2
                 n2 = Middle   2 n1 n3
                 n3 = Middle   3 n2 n4
                 n4 = Middle   4 n3 n5
                 n5 = RightEnd 5 n4
              in n1

    returnFirst :: DoubleList a -> DoubleList a
    returnFirst (Middle _ prev _) = returnFirst prev
    returnFirst (RightEnd _ prev) = returnFirst prev 
    returnFirst firstNode = firstNode

    returnPrev :: DoubleList a -> DoubleList a
    returnPrev (Middle x fst@(LeftEnd _ _) _ ) = fst
    returnPrev (Middle x mid@(Middle _ _ _) _ ) = mid
    returnPrev (RightEnd x prev) = prev
    returnPrev leftEnd = leftEnd

    returnNext :: DoubleList a -> DoubleList a
    returnNext (LeftEnd x nxt) = nxt
    returnNext (Middle x prev nxt) = nxt
    returnNext (RightEnd _ prev) =  prev

Answer 1

instance Functor DoubleList where
    fmap f (LeftEnd a nxt) = LeftEnd (f a) (fmap f nxt)
    fmap f (Middle a prev nxt) = Middle (f a) (fmap f prev) (fmap f nxt)
    fmap f (RightEnd a prev) = RightEnd (f a) (fmap f prev)

对构造函数的每次调用都代表一个新节点，对fmap的每次调用都代表对数据结构的一次单独遍历。在 create 的定义中，您使用 let 绑定来确保共享节点，但 fmap 的定义不会保留该共享。但是，您实际上无法从正常的安全代码中 观察到。

它起作用的原因是你的数据结构的字段是惰性的，所以你的 fmap 可以递增地产生结果： pattern-matching 在 fmap f create 的结果上计算到构造函数 (LeftEnd / Middle / RightEnd) 并且不评估字段。这意味着即使 create 包含引用循环，在将函数映射到它上面并检查结果时，您也不会运行进入无限循环。

它不的原因是它重复工作。如果它可以保留输入中的共享，则结果的结构将如下所示：

fmap f create
===
let n1' = LeftEnd  (f 1) n2'
    n2' = Middle   (f 2) n1' n3'
    n3' = Middle   (f 3) n2' n4'
    n4' = Middle   (f 4) n3' n5'
    n5' = RightEnd (f 5) n4'
in n1'

但实际上，它的结构是这样的：

let n1' = LeftEnd  (f 1) n2'
    n2' = Middle   (f 2) (fmap f n1) (fmap f n3)
in n1'

请注意，n2' 不包含对新 n1' 的任何引用，它包含一个 thunk，该 thunk 将构造一个恰好等同于 n1' 的值。所以你写的是一个有效的 Functor 实例，但它可能会使用比你预期更多的内存，这取决于你如何遍历结果。这个数据结构并不是真正的 doubly-linked 列表，它是一个（可能是无限的）计算树，其中每个节点可能有 1 或 2 个子节点。

通过因式分解，它等同于此，您可以将其视为一种无限的值流，可以在每个点一分为二：

-- An infinite <3 -ary tree.
data LoveTree a
  = LoveTree a (These (LoveTree a) (LoveTree a))

-- Using ‘Data.These.These’:
data These a b = This a | That b | These a b

Haskell 双链表函子

Haskell Doubly Linked List Functor

haskell

lazy-evaluation

functor