How to properly implement a helper function in Haskell

Question

The 'gridList' function description:

Takes two Integer inputs, x and y, and returns a list of tuples representing the coordinates of each cell from (1,1) to (x,y).

Example Output

$> gridList 3 3
$> [(1,1),(2,1),(3,1),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

Source Code

gridList :: Integer -> Integer -> [(Integer,Integer)]
gridList 1 1 = [(1,1)]
gridList 1 y = helper 1 y
gridList x y = (helper x y) ++ gridList (x-1) y
  where 
    helper :: Integer -> Integer -> [(Integer, Integer)]
    helper x 1 = [(x,1)]
    helper x y = (x,y) : (helper x (y-1))

Question: The code doesn't compile giving the following error: Variable not in scope referring to the line 3 where the helper is first introduced. Why doesn't the wheresolve this problem?

Thanks

The scope of a where is just the single definition (equals sign) above it. You need to either pull the helper out of the where, or convert the main gridList patterns into another helper. — luqui
– luqui, Commented Mar 31, 2020 at 22:08
Side note: you'll likely want to rework your algorithm, as this gridList won't produce the pairs in the order you expect. — duplode
– duplode, Commented Mar 31, 2020 at 22:27
The easiest way to implement this function is probably with a list comprehension. You can define it in a single line, which will be easily comprehensible to anyone familiar with the language. — Robin Zigmond
– Robin Zigmond, Commented Apr 1, 2020 at 6:20

Fyodor Soikin · Accepted Answer · 2020-03-31 22:32:10Z

5

In Haskell, where-bound definitions are in scope only in the equation immediately above the where block. This means that if you define a function using multiple equations, each of them gets a separate where block.

In your case, the definition of helper is in scope only for the third equation (line 4), but not for the first two.

In order to use the same helper definition for all branches, change the definition from three separate equations to a case expression:

gridList :: Integer -> Integer -> [(Integer,Integer)]
gridList x y = case (x, y) of
    (1, 1) -> [(1,1)]
    (1, _) -> helper 1 y
    _ -> (helper x y) ++ gridList (x-1) y
  where 
    helper :: Integer -> Integer -> [(Integer, Integer)]
    helper x 1 = [(x,1)]
    helper x y = (x,y) : (helper x (y-1))

answered Mar 31, 2020 at 22:32

Fyodor Soikin

81.3k10 gold badges134 silver badges179 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Luke Wanless Over a year ago

Thanks for such a clear answer! makes perfect sense now

amalloy Over a year ago

As an aside, this answer has some extraneous parentheses I think it'd be better style to remove: both uses of helper don't need parens.

Fyodor Soikin Over a year ago

It's a conscious choice @amalloy: I try to minimize changes to the OP's code besides those necessary to answer the question. This way there is less chance of confusion.

amalloy Over a year ago

Ah, I didn't notice you'd copied those sections directly. I agree, good decision to leave the parens alone.

CN_Cabbage Over a year ago

However, the output isn't the same as the example which starts from (1,1). I've tried to replace++ with : raising an error. How to fix this?

duplode · Accepted Answer · 2020-03-31 22:42:25Z

4

The problem is that the scope of the where-clause covers only the last equation. I'd usually suggest using a case-expression instead of multiple equations. However, since you are doing pattern matches on two arguments, doing that here requires either matching on a pair, as in Fyodor Soikin's answer, or nested case-expressions:

gridList :: Integer -> Integer -> [(Integer,Integer)]
gridList x y = case x of
    1 -> case y of
        1 -> [(1,1)]
        _ -> helper 1 y
    _ -> helper x y ++ gridList (x-1) y
    where 
    helper :: Integer -> Integer -> [(Integer, Integer)]
    helper x 1 = [(x,1)]
    helper x y = (x,y) : helper x (y-1)

The least invasive workaround is probably using pattern guards:

gridList :: Integer -> Integer -> [(Integer,Integer)]
gridList x y
    | 1 <- x, 1 <- y = [(1,1)]
    | 1 <- x = helper 1 y
    | otherwise = helper x y ++ gridList (x-1) y
    where
    helper :: Integer -> Integer -> [(Integer, Integer)]
    helper x 1 = [(x,1)]
    helper x y = (x,y) : helper x (y-1)

As luqui suggests, other options include pulling helper out of the where-clause, and pushing the equations inside it (gridList = go where go 1 1 = [(1,1)] -- etc.).

edited Mar 31, 2020 at 22:42

answered Mar 31, 2020 at 22:28

duplode

34.5k7 gold badges88 silver badges159 bronze badges

1 Comment

luqui Over a year ago

Oh interesting I hadn't considered replacing patterns with pattern guards to solve this sort of pattern

Collectives™ on Stack Overflow

How to properly implement a helper function in Haskell

2 Answers 2

5 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related