Implementing (+++) to Join JoinList's Related to this question, I wrote the (+++) function to join 2 JoinList's:

(+++) :: Monoid m =&gt; JoinList m a -&gt; JoinList m a -&gt; JoinList m a
(+++) Empty               y                    = y
(+++) x                   Empty                = x
(+++) left@(Single _ _)   right@(Single _ _)   = Append (tag $ Append mempty left right) left right
(+++) left                right                = Append (tag left `mappend` tag right) left right


Calling (+++) on jl1 and jl2 results in:

jl1 :: JoinList (Product Integer) String
jl1 = Append (Product 100) (Single (Product 25) "foo") (Single (Product 4) "bar")

jl2 :: JoinList (Product Integer) String
jl2 = Append (Product 50) (Single (Product 25) "bippy") (Single (Product 2) "baz")


Testing

*JoinList&gt; (+++) jl1 jl2
Append (Product {getProduct = 5000}) 
          (Append (Product {getProduct = 100}) 
               (Single (Product {getProduct = 25}) "foo") 
               (Single (Product {getProduct = 4}) "bar")) 
          (Append (Product {getProduct = 50}) 
               (Single (Product {getProduct = 25}) "bippy") 
               (Single (Product {getProduct = 2}) "baz"))
(I didn't know about the other JoinList questions when I was answering the other one one you asked.)

The case

(+++) left@(Single _ _)   right@(Single _ _)   =
  Append (tag $ Append mempty left right) left right


is redundant. There is no need to distinguish this case, also there is no need to call tag on a temporarily created Append value. Other than that, it looks good.

Just a remark, using Product with JoinList probably isn't very meaningful, monoids that provide useful information (depending on the use-case) would be Sum, Min or Max.

For testing, I'd suggest you to study QuickCheck. It allows you to define properties of your operations and automatically test them for various inputs. It's important to define good properties, in particular they should be distinct from the implementation of your operations. For example, you might want to test: For any JoinLists xs and ys


if i &lt; sizeJ xs then indexJ i (xs +++ ys) === indexJ i xs
if i &gt;= sizeJ xs then indexJ i (xs +++ ys) === indexJ (i - sizeJ xs) ys


etc.