A Haskell List Involving Recursion and High Order Functions

Question

Now I have this code that takes a list and does something to the first element and then to every other one. And it returns a list of the transformed elements. The problem I am having is that I want to have a list that contains the untransformed and the transformed elements. This is what I have so far:

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

The error it is giving me says there is a problem with the : y part of the function

Possible duplicate of High Order Function With Recusion in Haskell — amalloy
– amalloy, Commented Oct 21, 2017 at 5:32
For future reference, you should include the error message as part of your question. It not only helps those trying to answer but will help people find your question in the future if they have a similar problem and try searching on the error message. — K. A. Buhr
– K. A. Buhr, Commented Oct 21, 2017 at 6:00

K. A. Buhr · Accepted Answer · 2017-10-21 06:15:50Z

When I try your code, I get the following (admittedly somewhat lengthy and confusing) error message:

EveryOther.hs:4:42: error:
    • Couldn't match type ‘b’ with ‘a’
      ‘b’ is a rigid type variable bound by
        the type signature for:
          applyToEveryOther :: forall a b. (a -> b) -> [a] -> [b]
        at EveryOther.hs:1:22
      ‘a’ is a rigid type variable bound by
        the type signature for:
          applyToEveryOther :: forall a b. (a -> b) -> [a] -> [b]
        at EveryOther.hs:1:22
      Expected type: [a]
        Actual type: [b]
    • In the second argument of ‘(:)’, namely ‘applyToEveryOther f xs’
      In the second argument of ‘(:)’, namely
        ‘y : applyToEveryOther f xs’
      In the expression: f x : y : applyToEveryOther f xs
    • Relevant bindings include
        xs :: [a] (bound at EveryOther.hs:4:26)
        y :: a (bound at EveryOther.hs:4:24)
        x :: a (bound at EveryOther.hs:4:22)
        f :: a -> b (bound at EveryOther.hs:4:19)
        applyToEveryOther :: (a -> b) -> [a] -> [b]
           (bound at EveryOther.hs:2:1)

However, it's worth trying to figure out what GHC is saying here. As per the second bullet point, GHC was processing the subexpression y : applyToEveryOther f xs, and specifically looking at the second argument to the : operator in that expression (namely applyToEveryOther f xs. It expected that expression to have type [a], but the actual type of the expression was type [b].

Here, a and b are both "rigid" types, meaning simply that they were specified explicitly by the programmer. GHC also notes, in the relevant bindings, that y had type a.

So, to sum up, you asked GHC to evaluate the expression:

y : applyToEveryOther f xs

where you already specified that y had type a and applyToEveryOther f xs had type [b], and GHC refused to do this because lists in Haskell can't mix two different types.

And that's kind of the key to the whole problem. You want to transform some of the elements of your [a] list from a to b, but then you want to return a mixed list of as and bs. Haskell can't do that!

The only way your function can work is if you change the signature so that a and b are the same type:

applyToEveryOther :: (a -> a) -> [a] -> [a]

and your code will work fine.

Another way you could "discover" the correct signature is to leave it out and have Haskell infer the most general possible signature. If you load the code (without the explicit signature) into GHCi and ask for the type, you get:

> :t applyToEveryOther
applyToEveryOther :: (a -> a) -> [a] -> [a]
>

which is the most general possible type for this function.

val · Accepted Answer · 2017-10-21 14:35:10Z

0

If I understood correctly you wanted both, the original and transformed values.

However evaluating applyToEveryOther (+3) [0,1,2] returns [3,1,5]. If you want [0,3,1,4,2,5] as a result, try

applyToEveryOther _ [] = []
applyToEveryOther f [x] = [x,f x]
applyToEveryOther f (x:xs) = x: f x : applyToEveryOther f xs

answered Oct 21, 2017 at 14:35

val

12 bronze badges

Collectives™ on Stack Overflow

A Haskell List Involving Recursion and High Order Functions

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related