Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell reuse patterns

In the code below, the same pattern match (Node n left right) is used by three different functions. If I want to add a pattern, e.g. (Node n (Leaf) (Leaf)) or change my datatype, I have to change all the functions. Is there a way to reuse these patterns, so I only have to define them once?

data Tree = Node Int Tree Tree
          | Leaf 

add :: Tree -> Int -> Tree
add (Node n left right) x = Node (n+x) (add left x) (add right x) 
add (Leaf) x = Leaf

subtract :: Tree -> Int -> Tree
subtract (Node n left right) x = Node (n-x) (subtract left x) (subtract right x) 
subtract (Leaf) x = Leaf

swap :: Tree -> Tree
swap (Node n left right) = Node n right left
swap (Leaf) = Leaf

I tried

matchNode = (PNode n left right)
add matchNode x = Node (n+x) (add left x) (add right x) 

but it won't allow me to use the pattern _, and I can't extract n, left, and right from it.

like image 423
Emiel Steerneman Avatar asked Jul 03 '15 22:07

Emiel Steerneman


1 Answers

This only answers the part:

If I want to [...] change my datatype, I have to change all the functions.

In that case, you can avoid to change all the functions by defining a custom pattern with the pattern synonyms extension:

{-# LANGUAGE PatternSynonyms #-}

-- The old type:
-- data Tree = Node Int Tree Tree
--           | Leaf 

-- The new type
data Tree = NewNode Tree Int Tree  -- changed name & argument order
          | Leaf

pattern Node n left right = NewNode left n right

add :: Tree -> Int -> Tree
add (Node n left right) x = Node (n+x) (add left x) (add right x) 
add (Leaf) x = Leaf

-- etc.

Above, I renamed the old constructor Node into NewNode, also changing the order of its arguments. Then, I defined a pattern Node as a compatibility bridge, making the old patterns below work once again.


The question also asks:

Is there a way to reuse these patterns, so I only have to define them once?

@PyRulez commented on using record wildcards to shorten patterns. Here's a possible way:

{-# LANGUAGE ViewPatterns, RecordWildCards #-}

-- an auxiliary record type to define the custom pattern 
data R = RNode { left::Tree , n::Int, right::Tree } | RLeaf
-- a function to convert a Tree to a R
toR :: Tree -> R
toR (NewNode l n r) = RNode l n r
toR _ = RLeaf

-- Here we use a shorter pattern:
add2 :: Tree -> Int -> Tree
add2 (toR -> RNode{..}) x = Node (n+x) (add2 left x) (add2 right x)
  -- ^^^^^^^^^^^^^^^^^^^ this brings in scope left, n, right
add2 (toR -> RLeaf) x = Leaf

In this specific case, there's not a huge gain in space. However, no matter how large the pattern is, after the record definition (and auxiliary function) we only have to write toR -> RNode{...}.

I am not sure I really like this, though.

First, the record pollutes the global name space with three (partial!) functions left :: R -> Tree, n :: R -> Int, right :: R -> Tree. This will trigger a few warnings if you try to use e.g. n as an argument of another unrelated function (The local name shadows the global name n).

Second, the record wildcards extension brings in scope some variables which are not written in the code -- the reader has to know (or guess) what these variables are. Also note that the RNode{..} pattern brings e.g. n into scope with a different type than the global name: Int rather than R -> Int. A reader may think that n is the global one and be misled even at the type level.

Third, the code above uses view patterns, and these currently confuse the exhaustiveness checker:

Patterns.hs:23:1: Warning:
    Pattern match(es) are non-exhaustive
    In an equation for ‘add2’: Patterns not matched: _ _

In this specific case, we could simply write

add2 :: Tree -> Int -> Tree
add2 (node -> RNode{..}) x = Node (n+x) (add2 left x) (add2 right x)
add2 _ x = Leaf

to avoid the warning, but we do not always have that option, in general.

like image 109
chi Avatar answered Oct 23 '22 04:10

chi