Можно ли использовать uniplate «UniverseBi» для извлечения узлов «в ширину»? - PullRequest
Новая
       57

Можно ли использовать uniplate «UniverseBi» для извлечения узлов «в ширину»?

1 голос
/ 10 июля 2020

Можно ли использовать Uniplate universeBi для получения вывода в порядке ширины? Похоже, что результаты возвращаются в первую очередь в глубину. Мне интересно, как я могу использовать 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]. Возможно ли это в униплате?

1 Ответ

1 голос
/ 12 июля 2020

Вы можете покопаться в структуре 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 примитивов, если вам нужно.

...