beginner/learner implementation of foreach in haskell

Question

I am trying to implement a foreach morphism so as to test my understanding of morphism definition and pattern-matching... Obviously I miss both points completely.

Could you correct me ? I want the morphism foreach to takes a list of a and a morphism f as arguments and to return the list of all the results r of f applied to all a elements.

foreach :: [a] → f → [r]
foreach [] f = []
foreach x:[] f = (f x):[]
foreach []:x f = []:(f x)
foreach (x:xs) f = (f x) : (foreach (xs f))

When compiled, I have src\Main.hs:23:0: Parse error in pattern

Answer 1

The problem is syntactic, in this line:

foreach x:[] f = (f x):[]

Constructor application in patterns usually need to be parenthesized. This would work:

foreach (x:[]) f = (f x):[]

Incidentally... function application is highest precedence, so on the other hand you don't need parentheses on the right-hand side:

foreach (x:[]) f = f x:[]

The above holds for any infix constructor, but as a final note, for lists in particular there is a special syntax:

foreach [x] f = [f x]

There are other issues with your code as it stands, but that's the immediate error. A quick overview of the other problems:

foreach :: [a] → f → [r]

Type variables are implicitly universally quantified, so this means any type f. You need a more specific type, namely a -> r.

foreach x:[] f = (f x):[]

This is unnecessary--the recursive case will work correctly here, applying f to x and calling itself on the tail, giving the empty list case.

foreach []:x f = []:(f x)

I don't think this means what you think it means--this is pattern matching the head of a list against the empty list [], implying that the function is working on a list of lists.

foreach (x:xs) f = (f x) : (foreach (xs f))

The parentheses here are either unnecessary or incorrect. Again, function application has higher precedence than operators like :. Additionally, (xs f) means applying xs to f, as if it were a function. To apply foreach to two arguments, simply foreach xs f will suffice.

---

For comparison, here's the source code for the (identical except for argument order) standard library function map:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Answer 2

The type signature you give, is (at least in the Haskell compiler's opinion) bogus. It's a function which takes a list of items of any a and a value of any type f, and produces a list of values of any type r. It's like saying "I have a bunch of elephants and a screwdriver. Turn each elephant into a mango".

It seems your goal is to implement the map function:

map :: (a -> b) -> [a] -> [b]

Of course, it's perfectly valid to flip the arguments:

foreach :: [a] -> (a -> b) -> [b]

Your implementation is pretty close, but there are a few issues.

The biggest thing is to bear in mind that you're working with lists, not arrays. The : operator, also known as "cons", takes an item and prepends it to a list (e.g. 1 : [2,3,4]). You can't use it to arbitrarily concatenate items and lists, as you do in []:(f x). There is the ++ operator which concatenates two lists (e.g. [f x] ++ xs, which is the same as (f x) : xs), but you shouldn't need it to implement foreach.

Lastly, (foreach (xs f)) doesn't do what you may think it does. It is not like foreach(xs,f) in a C-style language, it is like foreach(xs(f)). (xs f), by itself, is like using xs as a function and applying f as the argument. Instead, you want (foreach xs f).

I will stop here, to avoid giving away too much. One little tidbit though: function application has higher precedence than any operator, so instead of (f x) : (foreach xs f), you can say f x : foreach xs f.