CODEWITHSUNDEEP
haskell
sof
sof

Reputation: 9649

Reverse own list a more optimal way

Tried to mimic the reverse function to the ADT List below,

 data List a = Nil | Cons a (List a) deriving (Show)                                                                   

 reverseList = convert . reverse'                                                                                      
     where                                                                                                             
         reverse' Nil = []                                                                                             
         reverse' (Cons x list) = reverse' list ++ [x]                                                                 

         convert [] = Nil                                                                                              
         convert (x:xs) = Cons x (convert xs)

The reverseList is composed of convert and reverse', how to achieve it optimally for instance without the aid of the built-in list?

Upvotes: 1

Views: 220

Answers (4)

chi
chi

Reputation: 116139

In my view, the most basic O(N) solution is to use recursion and an accumulator:

revlist :: List a -> List a
revlist xs = go xs Nil
   where
   go ::  List a -> List a -> List a
   go Nil         zs = zs
   go (Cons y ys) zs = go ys (Cons y zs)

This exploits go, a tail-recursive function which essentially uses the two lists as stacks, repeatedly popping elements form the first stack and pushing them to the second stack. Once the first stack is empty, the second stack contains the reversed list.

Upvotes: 2

MikaelF
MikaelF

Reputation: 3645

Starting from this answer to a similar question, you can let the compiler derive a Traversable instance to your List type:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}

data List a = Nil | Cons a (List a) deriving (Show, Functor, Foldable, Traversable)
--You need the Functor and Foldable instances

Then, reverse' becomes simply:

reverse' = foldl (flip Cons) Nil

which is O(N) time complexity.

Upvotes: 2

Redu
Redu

Reputation: 26161

You may perhaps do it in an applicative style efficiently. It should be O(n)

data List a = Nil | Cons a (List a) deriving Show

conc :: List a -> List a -> List a
conc Nil xs = xs
conc (Cons x xs) ys = Cons x $ conc xs ys

revlist :: List a -> List a
revlist xs = go xs Nil                                  -- invoke go xs function by Nil
             where
             go ::  List a -> (List a -> List a)
             go Nil         = conc Nil                  -- such as ([]++)
             go (Cons x xs) = go xs . conc (Cons x Nil) -- such as go xs . ([x]++)

λ> revlist (Cons 1 (Cons 2 (Cons 3 Nil)))
Cons 3 (Cons 2 (Cons 1 Nil))

We are nesting the concatenation operations (conc) to the right. This is basically difference lists.

Upvotes: 1

Robin Zigmond
Robin Zigmond

Reputation: 18249

All you need to do is translate all the list functions you're using to ones on your List type. Here this means ++ - let's define this for your version, and call it say listConcat (feel free to come up with your own name):

listConcat :: List a -> List a -> List a
listConcat Nil as = as
listConcat (Cons a as) bs = Cons a (listConcat as bs)

And then you can just translate the definition of reverseList that you already have:

reverseList :: List a -> List a
reverseList Nil = Nil
reverseList (Cons a as) = listConcat (reverseList as) (Cons a Nil)

Upvotes: 1

Related Questions