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 (++)?
Asked
Active
Viewed 4,343 times
1
user2840552
- 23
- 1
- 5
-
2What's wrong with using the concatenation operator? – Graham Laming Oct 14 '13 at 07:22
-
I want a more efficient way, from the perspective of complexity. – user2840552 Oct 14 '13 at 07:27
-
`(++)` is as good as it gets, for lists. – leftaroundabout Oct 14 '13 at 08:47
-
what is the complexity of ++ in haskell? – eternauta Dec 02 '15 at 14:50
3 Answers
2
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
- all possibilities of dividing a list in two in Haskell
- is it possible to do quicksort of a list with only one passing?
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 = []
0
If you want to stick to List, you can use join (>>=) like so: func a b = [a, b] >>= func'.
Nicolas
- 24,509
- 5
- 60
- 66
-
1I didn't notice the comment about complexity. With lazy evaluation neither (++) nor >>= are costly. – Nicolas Oct 14 '13 at 08:50