CODEWITHSUNDEEP
listhaskellconcatenation
user2840552
user2840552

Reputation: 23

Haskell efficient concatenation of lists

When I have a function

func :: Int -> Int -> [[a]]
func a b = func' a ++ func' b

where

func' :: Int -> [[a]],

what is a good possibility to avoid the (++)?

Upvotes: 1

Views: 4381

Answers (3)

Will Ness
Will Ness

Reputation: 71070

There is a general "difference list" technique for (++) elimination by rewriting a function to use extra argument such that f a b == g a ++ b.

You can see it used e.g. in

In your case this means rewriting func to incorporate the func' functionality by essentially inlining the (++), e.g.:

func :: Int -> Int -> [[a]]
func a b = go a 1 where 
  go _ _ = _ : _
  go _ _ = _ : _            -- replicate func' code, except
  go _ 1 = {- [] -} go b 0  -- the base case 
  go _ 0 = []

Upvotes: 2

Nicolas
Nicolas

Reputation: 24759

If you want to stick to List, you can use join (>>=) like so: func a b = [a, b] >>= func'.

Upvotes: 0

Satvik
Satvik

Reputation: 11208

Sequence is an alternative to lists which has many operation implemented efficiently.

Upvotes: 6

Related Questions