时间戳

首页 > 解决方案 > uniplate 的 `universeBi` 可以用于以广度优先方式检索节点吗？

haskell - uniplate 的 `universeBi` 可以用于以广度优先方式检索节点吗？

问题描述

是否可以使用 UniplateuniverseBi获得广度优先的输出？结果似乎以深度优先的方式返回。我想知道如何使用 uniplate 以universeBi广度优先的方式检索。

为了说明，请考虑以下玩具程序：

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Data
import Data.Generics.Uniplate.Data

data A = A B Int deriving (Data, Typeable)
data B = B Int   deriving (Data, Typeable)

val :: A
val = A (B 1) 2

ints :: [Int]
ints = universeBi val

我得到：

*Main> ints
[1,2]

但这是深度优先的，正如1从B节点获得的那样。我宁愿以广度优先的顺序得到它，即接收[2,1]。这在单板中可以实现吗？

标签： haskellgeneric-programminguniplate

解决方案

您可以深入研究Str返回的结构biplate：

layers :: Str a -> [[a]]
layers Zero = []
layers (One x) = [[x]]
layers (Two f x) = catLayers (layers f) ([] : layers x)
  where catLayers [] ys = ys
        catLayers xs [] = xs
        catLayers (x : xs) (y : ys) = (x ++ y) : catLayers xs ys
layersBi :: Biplate from to => from -> [[to]]
layersBi = layers . fst . biplate
breadthBi :: Biplate from to => from -> [to]
breadthBi = concat . layersBi

所以现在

breadthBi (A (B 1) 2) :: [Int]
-- = [2, 1]

和

data Tree a = Branch (Tree a) a (Tree a) | Leaf deriving (Data, Typeable)
--       4
--   2       6
-- 1   3   5   7
example = Branch (Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)) 4 (Branch (Branch Leaf 5 Leaf) 6 (Branch Leaf 7 Leaf))
(layersBi :: Data a => Tree a -> [[a]]) example
-- = [[],[4],[2,6],[1,3,5,7]]

我不确定它是否真的能保证Str准确地反映数据类型的结构，但它似乎可以。如果必须的话，您可以改为从原语中烹制一些东西Data。

推荐阅读