Why can foldr take a function with three arguments?

Question

I was having a look at some list operations and came across !!:

(!!)                    :: [a] -> Int -> a
xs !! n
  | n < 0     = negIndex
  | otherwise = foldr (\x r k -> case k of
                                   0 -> x
                                   _ -> r (k-1)) tooLarge xs n

The function (\x r k -> ...) has type a -> (Int -> a) -> Int -> a, but foldr takes a function that should only accept two arguments:

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Can someone explain to me why foldr accepts a function that takes 3 arguments with the following type a -> (Int -> a) -> Int -> a? Especially since the result should have the same type as the second argument?

Questions like this are asked about foldr often, but I can't find anything good enough to mark this as a duplicate of. Anyone have an idea? The best I could find are https://stackoverflow.com/q/15879940/625403 and https://stackoverflow.com/q/4733019/625403. — amalloy, Jul 07 '17 at 20:12
`->` in types is right associative. Your function type can also be written `a -> (Int -> a) -> (Int -> a)`. — melpomene, Jul 07 '17 at 20:29
Yeah, I see that with such step function `r` is out `go` that already has `ys` and waits for `(k-1)`, question can be closed, thanks to all — srghma, Jul 07 '17 at 20:44
With more parens added - foldr takes a function `fn :: a -> (Int -> a) -> (Int -> a)` and returns a value of type `(Int -> a)`. After foldr is done this n gets applied to this function: `(foldr fn tooLarge xs) n`. — user8242965, Jul 07 '17 at 23:31
@amalloy neither is an exact duplicate. This question can be rewritten as "why can foldr take a function with three arguments?". — Zeta, Jul 08 '17 at 09:29

score 3 · Accepted Answer · answered Jul 08 '17 at 09:35

3

-> is right-associative. So a -> b -> c is a -> (b -> c). Therefore, your type

a -> (Int -> a) ->  Int -> a

is the same as

a -> (Int -> a) -> (Int -> a)

and we can see that it fits foldr's type quite well.

answered Jul 08 '17 at 09:35

Zeta

103,620
13
194
236

score 2 · Answer 2 · answered Feb 24 '19 at 18:20

(more explanation for others ;)

(!!)                    :: [a] -> Int -> a
xs !! n
  | n < 0     = negIndex
  | otherwise = foldr (\x r k -> case k of
                                   0 -> x
                                   _ -> r (k-1)) tooLarge xs n

foldr            :: (a -> b -> b) -> b -> [a] -> b
--                                   ^1          ^2

foldr commonly makes an accumulated(?) value. In this case, foldr makes an accumulated function (b) of the type (Int -> a)! foldr ... tooLarge xs is evaluated to an accumulated function, and this accumulated function (^2) takes an argument n. ^1 is a tooLarge function. Interestingly, the buildup of this accumulated function depends on the value of a free variable n (i.e., k).

For example, ['a', 'b', 'c'] !! 2 is evaluated like below:
\x r k = \'a' r 2 -> r (2-1) (r is not known yet, and drives further evaluations.)
\x r k = \'b' r 1 -> r (1-1)
\x r k = \'c' r 0 -> 'c'

['a', 'b', 'c'] !! 3 goes like this:
\x r k = \'a' r 3 -> r (3-1)
\x r k = \'b' r 2 -> r (2-1)
\x r k = \'c' r 1 -> r (1-1) (r turns out to be tooLarge.) = tooLarge (1-1) (ERROR!)

You can check debug traces:

module Main where

import Debug.Trace

tooLarge _ = errorWithoutStackTrace "!!!: index too large"
negIndex = errorWithoutStackTrace "!!!: negative index"

(!!!)                    :: Show a => [a] -> Int -> a
xs !!! n
  | n < 0     = negIndex
  | otherwise = foldr (\x r k -> trace ("x: " ++ show x ++ ", k: " ++ show k) $
                                 case k of
                                   0 -> x
                                   _ -> r (k-1)) tooLarge xs n

main = do
  print $ ['a', 'b', 'c'] !!! 2
  print $ ['a', 'b', 'c'] !!! 3

-- x: 'a', k: 2
-- x: 'b', k: 1
-- x: 'c', k: 0
-- 'c'
-- x: 'a', k: 3
-- x: 'b', k: 2
-- x: 'c', k: 1
-- sample: !!!: index too large

This (!!) implementation is a report version. The report version of the prelude is more efficient than a familiar naive recursive implementation, due to optimizations of foldr.

Why can foldr take a function with three arguments?

2 Answers2