Haskell concat / filter according specific rules

Question

According to following rules, I tried to solve the following problem:

1. No definition of recursion
2. No List of Comprehension
3. Only Prelude-Module is allowed.

Now I have to implement higher-order for concat and filter.

Im at this point:

concat' :: [[a]] -> [a]
concat' a = (concat a)

filter' :: (a -> Bool) -> [a] -> [a]
filter' p [] = []
filter' p (x:xs) 
            | p x = x : filter p xs
            | otherwise = filter p xs

The concat function is working (nothing special so far) -> Is that a defined recursion? I mean I use the predefined concat from standard-prelude but myself I don't define it - or am I wrong?

For the filter, the function I've looked up the definition of standard prelude but that's either not working and it contains a definition of recursion.

Answer 1

I'm supposing the concat and filter functions should be avoided. Why would we need to implement concat and filter if they're already available? So try implementing them from scratch.

We can use folding instead of recursion and list comprehensions. The below solutions use the function foldr.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

concat' :: [[a]] -> [a]
concat' = foldr (++) []

filter' :: (a -> Bool) -> [a] -> [a]
filter' p = foldr (\x acc -> if p x then x:acc else acc) [] 

Examples:

main = do
  print $ concat' ["A", "B", "CAB"]    -- "ABCAB"
  print $ filter' (\x -> x `mod` 2 == 0) [1..9]  -- [2, 4, 6, 8]

Answer 2

You may do as follows;

concat' :: Monad m => m (m b) -> m b
concat' = (id =<<)

filter' p = ((\x-> if p x then [x] else []) =<<)

=<< is just flipped version of the monadic bind operator >>=.

filter' (< 10) [1,2,3,10,11,12]
[1,2,3]