1

Is it possible to use Uniplate's universeBi to get the output in breadth-first-order? It appears the results are returned in a depth-first fashion. I'm wondering how I can use uniplate to retrieve the universeBi in a breadth-first fashion.

To illustrate, consider the following toy program:

{-# 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

I get:

*Main> ints
[1,2]

But this is depth-first, as 1 is obtained from the B node. I'd rather get it in the breadth-first order, i.e., receive [2,1]. Is this achievable in uniplate?

alias
  • 28,120
  • 2
  • 23
  • 40
  • this doesn't seem supported by uniplate, but it's possible with the lower-level `Data.Data`/syb – Li-yao Xia Jul 10 '20 at 01:49
  • I don't think you're observing depth-first-ness here, just left-to-right-ness. The default instance of `Biplate` for a product type is roughly (pseudocode) `biplate (x, y) = concatTraversals (biplate x) (biplate y)`. If you switch the order of `A`'s fields you should get the `Int`s in a different order. – Benjamin Hodgson Jul 11 '20 at 23:12
  • @BenjaminHodgson Left-to-right traversal is a form of depth-first traversal (in-order traversal)? The example isn't particularly illustrative, but I'm assuming OP would want a a function that could perform breadth-first traversal on `data Tree = Branch Tree Int Tree | Leaf`. No rearrangement of the arguments of `Branch` will make `universeBi` work there. – HTNW Jul 12 '20 at 03:38

1 Answers1

1

You can dig into the structure of the Str returned by 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

So now

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

and

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]]

I'm not sure if it's actually guaranteed that Str exactly reflects the structure of the data type, but it appears to. You could instead cook something out of the Data primitives if you have to.

HTNW
  • 27,182
  • 1
  • 32
  • 60
  • Thanks! I was looking for a solution that didn't require looking "inside" the encoding, but it appears that is simply not possible. – alias Jul 12 '20 at 19:08