How do I concatenate two Snoc lists?

Question

I have to construct a Snoc list, the reverse of Cons. I've done to add one element forward i don't know how to concatenate two lists. That's the situation now:

module Tsil where

data Tsil a = Lin
            | Snoc (Tsil a, a)
            deriving (Eq, Ord, Show, Read)


empty :: Tsil a
empty = Lin

infixr 2 |: 
(|:) :: a -> Tsil a -> Tsil a
(|:) a t = Snoc (t, a)

infixr 5 |++
(|++) :: Tsil a -> Tsil a -> Tsil a 
(|++) a Lin = a
(|++) Lin a = a

Answer 1

Your list type is the same as Haskell's, so just make it a Haskell list, concatenate, convert back. Hooray for reusability in Haskell ;-)

toList Lin = []
toList (Snoc (xs, x)) = x : toList xs

toTsil [] = Lin
toTsil (x:xs) = Snoc (toTsil xs, x)

a (|++) b = toTsil $ toList a ++ toList b

Answer 2

(|++) l (Snoc (t,x)) = Snoc (l |++ t,x)