CODEWITHSUNDEEP
haskell
AnchovyLegend
AnchovyLegend

Reputation: 12538

Using List Comprehension in place of Recursion

I am curious whether or not using list comprehension in place of recursion is possible for the following example.

The function replaceFirst that takes in an an element and a list and replaces the first occurrence of the element from the list.

This can be done using recursion as follows:

replaceFirst _ [] = []
replaceFirst elem y (x:xs) | x==y = (elem:xs)
                           | otherwise = x:replaceFirst elem y xs

My question is, can this recursive function, or a similar recursive function that operates on the first occurrence of an element in a list, be replaced with a list comprehension function? Why or why not? (I am more concerned with the reasoning than the actual code).

Upvotes: 4

Views: 1346

Answers (2)

user2073990
user2073990

Reputation:

List comprehension, inspired by leftaroundabout:

replaceFirst elem y xs = [a | let b = break (==y) xs
                                  c = if not (null $ snd b) 
                                         then fst b ++ [elem] ++ tail (snd b) 
                                         else fst b
                              , a <- c]

Upvotes: 0

Don Stewart
Don Stewart

Reputation: 137947

List comprehensions are syntactic sugar for various forms of map, filter, and concatMap. If your recursive function can be described in terms of these, then you can rewrite it to a list comprehension. They can't short circuit, as you do above, nor can they pass accumulating state.

Your replaceFirst would seem to require an accumulator to "tell" later elements in the list about the appearance of earlier elements. I think this makes it difficult or impossible to write using only list comprehension syntax.

Upvotes: 8

Related Questions