Skip to content

GitLab

  • Menu
Projects Groups Snippets
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
  • GHC GHC
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,866
    • Issues 4,866
    • List
    • Boards
    • Service Desk
    • Milestones
    • Iterations
  • Merge requests 456
    • Merge requests 456
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Deployments
    • Deployments
    • Releases
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Code review
    • Insights
    • Issue
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #19112
Closed
Open
Created Dec 23, 2020 by Carter Schonwald@carterDeveloper

pattern synonyms and rewrite rules - how can/should they interact?

So i'm sprucing up a random access list data structure i have, see here for the file and I've run into a (not super important ultimately) question that perhaps is a ghc blind spot:

what are the current vs forward looking ways to make rewrite rules better compose with/ interact with pattern synonyms, and might the case be that theres a gap there currently, and what would be ways to make them better?

is CONLIKE relevant here? or do i need to mess around with INLINE and inline phases?

for more concreteness

data RAList a = RNil
                | RCons {-# UNPACK #-}  !Word64 -- total number of elements, aka sum of subtrees
                        {-# UNPACK #-}  !Word64 --  size of this subtree
                                        (Tree a)
                                        (RAList a)

pattern Nil :: forall a. RAList a
pattern Nil = RNil

pattern Cons :: forall a. a -> RAList a -> RAList a
pattern Cons x xs <-( uncons -> Just(x,xs) )
 where Cons x xs = cons x xs
{-# COMPLETE Nil,Cons#-}

empty :: RAList a
empty = Nil

-- | Complexity /O(1)/.
cons :: a -> RAList a -> RAList a
cons x (RCons tots1 tsz1 t1
              (RCons _tots2 tsz2 t2 rest))
           | tsz2 == tsz1 = RCons (tots1 + 1) (tsz1 * 2 + 1 ) (Node x t1 t2 ) rest
cons x rlist  = RCons (1 + wLength rlist ) 1 (Leaf x) rlist


uncons :: RAList a -> Maybe (a, RAList a)
uncons (RNil) =  Nothing
uncons (RCons _tot _treetot  (Leaf h)     wts) =  Just (h,wts)
uncons (RCons _tot w (Node x l r) wts) = Just (x, (RCons (restsize + w2 + w2) w2 l (RCons (restsize + w2) w2 r wts)))
      where
        w2 = w `quot` 2
        restsize = wLength wts

then i have an adapted mini copy of the base list fusion operations adapted to my data structure


{-# INLINE [1] build #-}
--- a
build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> RAList a
build = \ g -> g  cons Nil

unfoldr :: (b -> Maybe (a, b)) -> b -> RAList a
{-# INLINE unfoldr #-} -- See Note [INLINE unfoldr  in ghc base library original source]
unfoldr f b0 = build (\c n ->
  let go b = case f b of
               Just (a, new_b) -> a `c` go new_b
               Nothing         -> n
  in go b0)


augment :: forall a. (forall b. (a->b->b) -> b -> b) -> RAList a -> RAList a
{-# INLINE [1] augment #-}
augment g xs = g cons xs



{-# RULES
"fold/build"    forall k z (g::forall b. (a->b->b) -> b -> b) .
                foldr k z (build g) = g k z

"foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
                foldr k z (augment g xs) = g k (foldr k z xs)


"augment/build" forall (g::forall b. (a->b->b) -> b -> b)
                       (h::forall b. (a->b->b) -> b -> b) .
                       augment g (build h) = build (\c n -> g c (h c n))

--- not sure if these latter rules will be useful for RALIST

"foldr/cons/build" forall k z x (g::forall b. (a->b->b) -> b -> b) .
                           foldr k z (Cons x (build g)) = k x (g k z)


"foldr/single"  forall k z x. foldr k z (Cons x Nil) = k x z
"foldr/nil"     forall k z.   foldr k z Nil  = z
#-}

i then get the following warnings because Cons and Nil are pattern synonyms rather than actual constructors


src/Data/RAList.hs:766:1: warning: [-Winline-rule-shadowing]
    Rule "foldr/cons/build" may never fire
      because ‘Data.RAList.$bCons’ might inline first
    Probable fix: add an INLINE[n] or NOINLINE[n] pragma for ‘Data.RAList.$bCons’
    |
766 | "foldr/cons/build" forall k z x (g::forall b. (a->b->b) -> b -> b) .
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

src/Data/RAList.hs:770:1: warning: [-Winline-rule-shadowing]
    Rule "foldr/single" may never fire
      because ‘Data.RAList.$bCons’ might inline first
    Probable fix: add an INLINE[n] or NOINLINE[n] pragma for ‘Data.RAList.$bCons’
    |
770 | "foldr/single"  forall k z x. foldr k z (Cons x Nil) = k x z
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

src/Data/RAList.hs:770:1: warning: [-Winline-rule-shadowing]
    Rule "foldr/single" may never fire
      because ‘Data.RAList.$bNil’ might inline first
    Probable fix: add an INLINE[n] or NOINLINE[n] pragma for ‘Data.RAList.$bNil’
    |
770 | "foldr/single"  forall k z x. foldr k z (Cons x Nil) = k x z
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

src/Data/RAList.hs:771:1: warning: [-Winline-rule-shadowing]
    Rule "foldr/nil" may never fire
      because ‘Data.RAList.$bNil’ might inline first
    Probable fix: add an INLINE[n] or NOINLINE[n] pragma for ‘Data.RAList.$bNil’
    |
771 | "foldr/nil"     forall k z.   foldr k z Nil  = z
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking