Help with countEven - ch4 of updated purescript book

Help
#1
  1. (Medium) Write a recursive function countEven which counts the number of even integers in
    an array. Hint: the function head (also available in Data.Array ) can be used to find the first
    element in a non-empty array.

I can’t figure out how to get my solution to type check. The result of head is Maybe a, but fromMaybe doesn’t seem to know what type it should extract to.

countEven :: Array Int -> Int
countEven arr =
    if null arr
        then 0
        --else if (2 `mod` 2) == 0
        --else if (fromMaybe [] $ head $ arr `mod` 2) == 0
        --else if ((head arr) `mod` 2) == 0
        else if ((fromMaybe [] (head arr)) `mod` 2) == 0
                then 1 + (countEven $ fromMaybe [] $ tail arr)
                else        countEven $ fromMaybe [] $ tail arr
#2

Looking at the type signature for fromMaybe:

fromMaybe :: forall a. a -> Maybe a -> a

it looks like you’re using fromMaybe like this:

let 
  result :: Maybe Int
  result = head arr

  usage = fromMaybe ([] :: forall anyType. Array anyType) result

I’m guessing the compiler is wondering how to unify Array anyType with Int, correct?

If you just write [], the compiler doesn’t know if that is an empty array of Ints or Strings or some other type. So, it’s likely asking you to further annotate the value with a type since it cannot infer it. Some thing like ([] :: Array Int).

Note: I’m only providing clarification on your question, not on how to solve this problem.

#3

fromMaybe is a function that ‘extracts’ a purescript value that’s wrapped in a Maybe.

Here’s how we might implement this naively:

fromMaybe :: forall a. Maybe a -> a
fromMaybe (Just value) = value {- value has type a -}
fromMaybe Nothing      = {- Uhm? How to return something of type a? -}

Right now, this is a partial function. It can’t cover all its inputs. The problem is that we don’t have anything to return in the case where Maybe a doesn’t have a value.

One solution is to upgrade this to take a default value with the right type.

fromMaybe :: forall a. a -> Maybe a -> a
fromMaybe fallback (Just value) = value    {- value has type a -}
fromMaybe fallback Nothing      = fallback {- fallback has type a -}

Back to your code. Consider the types here:

fromMaybe [] (head arr)

[] is an Array
head arr is Maybe Int

You’re asking fromMaybe to return an Int, and if it can’t, to return an empty array.

That would type something like this:

fromMaybe :: forall a b. a -> Maybe b -> Either a b
fromMaybe fallback (Just value) = Right value   {- value has type b -}
fromMaybe fallback Nothing      = Left fallback {- fallback has type a -}

arr :: Array Int
arr = ...

firstValue :: forall a. Either (Array a) Int
firstValue = fromMaybe [] (head arr)

Instead of the one we created here, fromMaybe has this type signature:

fromMaybe :: forall a. a -> Maybe a -> a

Instead of having two types (a and b), we have only one. Which tells us that the default value and the value being wrapped in the Maybe must have the same type.

[] and Int do not have the same type.

Instead, you could try something like:

fromMaybe 0 (head arr)

In this case, (0 :: Int) and ((head arr) :: Maybe Int) have types that work with fromMaybe.

2 Likes
#4

Thanks. This makes complete sense now. Of course it’s looking for an Int… and the default value of Array makes zero sense then.

#5

The easiest solution to it can be using filter:

> :paste
… 
…  import Data.Array
… 
… length :: forall a. Array a -> Int
… length arr = 
…     if null arr 
…         then 0
…         else 1 + length (unsafePartial tail arr)
…
… countEven arr = length (filter(\n -> n `mod` 2 == 0) arr)
… 
… countEven (1 .. 10)
… ^D
5

Hope this helps :slight_smile:

1 Like
#6

To avoid using unsafePartial or a bunch of fromMaybe, you can parse your Array into a NonEmptyArray. Instead of using fromMaybe with a default value, you can just pattern match. This is structurally similar to the answer given, only perhaps a bit easier to read.

import Data.Array.NonEmpty (NonEmptyArray, fromArray, head, tail)
import Data.Maybe (Maybe(..))

countEven :: Array Int -> Int
countEven = fromArray >>> countEven'
  where
  countEven' :: Maybe (NonEmptyArray Int) -> Int
  countEven' Nothing = 0
  countEven' (Just arr)
    | head arr `mod` 2 == 0 = 1 + countEven (tail arr)
    | true = countEven (tail arr)

I suppose you don’t really need those guards:

countEven :: Array Int -> Int
countEven = fromArray >>> countEven'
  where
  countEven' :: Maybe (NonEmptyArray Int) -> Int
  countEven' Nothing = 0
  countEven' (Just arr) = (if head arr `mod` 2 == 0 then 1 else 0) + countEven (tail arr)
#7

Pattern matching is definitely the way to go here, though that isn’t introduced until chapter 5 :frowning:. There’s an open issue to reorder things so that you can use the proper idiomatic techniques when solving this.

3 Likes