如何将指数转换为镜头，将森林转换为树木？

Question

我正在尝试制作一个函数，该函数将索引引入森林，并使用整数列表来选择树下的路径，并将其变成聚焦相同元素的透镜。

实际上，它与 (t :: Data.Tree.Forest) ^@.. itraversed <.> itraversed 的作用相反。

这是我的尝试：

pathToLens :: (Applicative f) => (Int, [Int]) -> LensLike' f (Data.Tree.Forest a) (Data.Tree.Tree a)
pathToLens (rootIdx, branchIndices) =
    ix rootIdx . helper branchIndices
  where
    helper :: (Applicative f) => [Word64] -> LensLike' f (Data.Tree.Tree a) (Data.Tree.Tree a)
    helper (idx : rest) = branches . ix idx . helper rest
    helper [] = id

函数编译正常。但后来我尝试使用它：

test = [Data.Tree.Node () []] ^. (pathToLens (0,[]))

我得到：

• No instance for (Monoid (Data.Tree.Tree ()))
    arising from a use of ‘pathToLens’
• In the second argument of ‘(^.)’, namely ‘(pathToLens (0, []))’

为什么我的树没有幺半群？从the Tree docs来看，好像有Monad Tree。那不包括幺半群树吗？

Answer 1

Why is there no Monoid for my Tree ?

似乎没有通用的方法来“添加”两棵玫瑰树，因为你很难决定和树的根标签应该是什么。因此，您不能为所有可能种类的 Tree 对象提供通用的 Monoid 实例。

但是，这里需要的只是类型 Tree () 的 Monoid 实例。和根标签只有一个可能的值，因此问题消失了。相关代码好写：

{-#  LANGUAGE  FlexibleInstances  #-}
import  Data.Tree

instance  Semigroup (Tree ())  where  tr1 <> tr2 = Node () [tr1,tr2]
instance  Monoid  (Tree ())    where  mempty = Node () []

如果这有帮助，您可以为任何 Tree m 类型创建一个 Monoid 结构，假设基本类型 m 是本身一个幺半群。像这样：

{-#  LANGUAGE  ScopedTypeVariables  #-}
{-#  LANGUAGE  ExplicitForAll       #-}

import Data.Tree

instance  Monoid m => Semigroup (Tree m)  where
    tr1@(Node r1 f1) <> tr2@(Node r2 f2) = Node (r1<>r2) [tr1,tr2]

instance  Monoid m => Monoid (Tree m)  where
    mempty = Node { rootLabel = (mempty::m), subForest = [] }

这段代码可以用 GHC 8.6.5 完美编译：

{-#  LANGUAGE  ScopedTypeVariables  #-}
{-#  LANGUAGE  ExplicitForAll       #-}

import  Data.Tree
import  Control.Lens
import  Control.Lens.Combinators
import  Data.Tree.Lens

pathToLens :: (Applicative f) => (Int, [Int]) -> LensLike' f (Data.Tree.Forest a) (Data.Tree.Tree a)
pathToLens (rootIdx, branchIndices) =
    ix rootIdx . helper branchIndices
  where
    helper :: (Applicative f) => [Int] -> LensLike' f (Data.Tree.Tree a) (Data.Tree.Tree a)
    helper (idx : rest) = branches . ix idx . helper rest
    helper [] = id

上面的实例代码使有关缺少 Monoid 实例的错误消息消失了：

在`ghci`下测试：

$ ghci
GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/jeanpaul/.ghci
 λ> 
 λ> :set -XScopedTypeVariables 
 λ> :set -XExplicitForAll
 λ> 
 λ> :!cat pathToLens.hs

import  Data.Tree
import  Control.Lens
import  Control.Lens.Combinators
import  Data.Tree.Lens

pathToLens :: (Applicative f) => (Int, [Int]) -> LensLike' f (Data.Tree.Forest a) (Data.Tree.Tree a)
pathToLens (rootIdx, branchIndices) =
    ix rootIdx . helper branchIndices
  where
    helper :: (Applicative f) => [Int] -> LensLike' f (Data.Tree.Tree a) (Data.Tree.Tree a)
    helper (idx : rest) = branches . ix idx . helper rest
    helper [] = id

 λ> 
 λ> :load pathToLens.hs
[1 of 1] Compiling Main             ( pathToLens.hs, interpreted )
Ok, one module loaded.
 λ> 
 λ> ls = (pathToLens (0,[]))
 λ> test = [Data.Tree.Node () []]  ^.  ls

<interactive>:10:36: error:
    • No instance for (Monoid (Tree ())) arising from a use of ‘ls’
    • In the second argument of ‘(^.)’, namely ‘ls’
      In the expression: [Node () []] ^. ls
      In an equation for ‘test’: test = [Node () []] ^. ls
 λ>

所以，在那个阶段，最初的问题重现了。

现在让我们为（一些）树添加我们的小幺半群实例，然后重试：

 λ> 
 λ> instance  Semigroup γ => Semigroup (Tree γ)  where  t1@(Node r1 f1) <> t2@(Node r2 f2)  =  Node  (r1<>r2)  [t1,t2]
 λ> 
 λ> instance  Monoid µ => Monoid (Tree µ)  where  mempty  =  Node { rootLabel = (mempty::µ), subForest = [] }
 λ> 
 λ> test = [Data.Tree.Node () []]  ^.  ls
 λ> 
 λ> :t test
test :: Tree ()
 λ>

Haskell Prelude 为 () 提供了一个（简单的）Monoid 实例，然后编译器从中推断出另一个 Monoid 实例的存在 Tree ().

Answer 2

鉴于给定路径上的树可能不存在，pathToLens 不是合适的镜头。镜头总能击中目标。

可以做成Traversal':

import Data.List.NonEmpty

pathToTraversal :: NonEmpty Int -> Traversal' (Data.Tree.Forest a) (Data.Tree.Tree a)
pathToTraversal (rootIdx :| branchIndices) =
    ix rootIdx . helper branchIndices
  where
    helper (idx : rest) = branches . ix idx . helper rest
    helper [] = id

而且，如果您喜欢冒险并相信 Traversal' 总能击中目标，则可以使用 unsafeSingular:

将其变成 Lens'

unsafePathToLens :: NonEmpty Int -> Lens' (Data.Tree.Forest a) (Data.Tree.Tree a)
unsafePathToLens is = unsafeSingular (pathToTraversal is)

如何将指数转换为镜头，将森林转换为树木？

How do I convert indices to a lens for a Forest to a Tree?

haskell

tree

haskell-lens

在`ghci`下测试：

如何将指数转换为镜头，将森林转换为树木？

How do I convert indices to a lens for a Forest to a Tree?

haskell

tree

haskell-lens

在ghci下测试：

在`ghci`下测试：