Haskell Tail Recursive Inner Functions

Question

Coming from a Scala background I'm pretty used to using tail recursion to write stuff that can't be easily represented using another method. Let's say I want to calculate the length of a list, but I don't want to use a fold. I want to do it in a natural tail recursive way. I thought of this way:

myLength :: [a]  -> Int
myLength x    = innerLength x 0

innerLength :: [a] -> Int -> Int  -- Tail recursive inner call
innerLength [] _      = 0
innerLength (x:xs) n  = innerLength xs n+1

and this works fine. But it isn't very readable that innerLength is really the tail recursive inner call to count the list members and it seems like innerLength is scoped in such a way someone could just use innerLength instead of the better myLength.

Is there a better way to do this?

Yeah, use a let or where clause in the definition of myLength. — Yawar
– Yawar, Commented Mar 7, 2015 at 18:04
innerLength xs n+1 is parsed as (innerLength xs n)+1, this is not tail-recursive. — Franky
– Franky, Commented Mar 7, 2015 at 18:29
What @Franky says, moreover innerLength [] _ = 0 throws away the accumulator instead of returning it. It should be innerLength [] n = n. I'd also be tempted to use strict application in the recursive case e.g. innerLength (_:xs) n = innerLength xs $! n+1 — chi
– chi, Commented Mar 7, 2015 at 18:33
@Franky Thanks for pointing that out. That seems to be a constant headache for me with haskell. — Steve
– Steve, Commented Mar 7, 2015 at 20:15

Community · Accepted Answer · 2017-05-23 12:12:52Z

4

Yes, you can either use let:

myLength :: [a]  -> Int
myLength x = 
    let innerLength :: [a] -> Int -> Int  -- Tail recursive inner call
        innerLength [] n      = n
        innerLength (x:xs) n  = innerLength xs (n+1)
    in innerLength x 0

Live demo

or where:

myLength :: [a]  -> Int
myLength x = innerLength x 0
    where innerLength :: [a] -> Int -> Int  -- Tail recursive inner call
          innerLength [] n      = n
          innerLength (x:xs) n  = innerLength xs (n+1)

Live demo

See here for the difference between the two.

edited May 23, 2017 at 12:12

CommunityBot

11 silver badge

answered Mar 7, 2015 at 18:18

sh03

76.5k39 gold badges177 silver badges282 bronze badges

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

2 Comments

kini Over a year ago

Well, innerLength [] n = n, really.

Jedai Over a year ago

Haskell style often name the auxiliary function just "go" or "aux" since its scope is limited to the function and the alternative is just a repetition of the function name slightly modified, which doesn't bring any readability benefits. Only the top level functions usually get explicit signatures, it is considered that local variables are close enough to the potential problems that they don't need one (except if you wish to clarify a particularly obscure type).

Collectives™ on Stack Overflow

Haskell Tail Recursive Inner Functions

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related