CODEWITHSUNDEEP
functionhaskelltypesargumentsfold
srghma
srghma

Reputation: 5353

Why can foldr take a function with three arguments?

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?

Upvotes: 7

Views: 785

Answers (2)

maczniak
maczniak

Reputation: 1092

(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.

Upvotes: 2

Zeta
Zeta

Reputation: 105935

-> 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.

Upvotes: 3

Related Questions