Haskell. Recursive Lambda. Errors

Question

y :: (f->f) -> f
y f = f (y f)

indexOf :: Char -> String -> Maybe Int
indexOf c l = 
    y(\ ff c (h:t) pos -> 
        if ( c == h) then Just pos
            else ff c t (pos + 1)
        )(c, l, 0)

indexOf c [] = Nothing

It gives me two compilation errors: The code should find position of char c in string. For example: indexOf('a', 'lamp') = 2

 Couldn't match expected type `[(Char, String, Integer)]
                                  -> Integer -> Maybe Integer'
                with actual type `Maybe Int'
    The lambda expression `\ ff c (h : t) pos -> ...'
    has four arguments,
    but its type `((Char, String, Integer) -> Maybe Int)
                  -> (Char, String, Integer) -> Maybe Int'
    has only two
    In the first argument of `y', namely
      `(\ ff c (h : t) pos
          -> if (c == h) then Just pos else ff c t (pos + 1))'
    In the expression:
      y (\ ff c (h : t) pos
           -> if (c == h) then Just pos else ff c t (pos + 1))
        (c, l, 0)


    Couldn't match expected type `[(Char, String, Integer)]
                                  -> Integer -> Maybe Integer'
                with actual type `Maybe Int'
    The function `ff' is applied to three arguments,
    but its type `(Char, String, Integer) -> Maybe Int' has only one
    In the expression: ff c t (pos + 1)
    In the expression: if (c == h) then Just pos else ff c t (pos + 1)

I don't know how to repair it. Please give me a hand :)

Haskell functions are called function a b c ... not function(a,b,c,...). The structure (a,b,c,...) is called a tuple, but the function defined doesn't take one. — AJF
– AJF, Commented Mar 5, 2016 at 23:55

Random Dev · Accepted Answer · 2016-03-05 22:26:28Z

4

the problem here is that you mix tuples and curried arguments (you should try to stay with the basic form of two curried arguments if you don't want to change y) - but your thinking is quite good!

indeed it's only a few small changes to get it working:

indexOf :: Char -> String -> Maybe Int
indexOf c ls = 
    y(\ ff (ls, pos) ->
       case ls of
         (h:t)
           | h == c -> Just pos
           | otherwise -> ff (t, pos+1)
         [] -> Nothing
     )(ls, 0)

as you can see I did:

moved the case-split inside
rewrote the arguments into a tuple of the rest-list and the position
reused the c from the closure you get for free ;)

here is it in action:

λ> indexOf 'l' "Hello"
Just 2
λ> indexOf 'a' "Hello"
Nothing

of course while this is a good exercise you should not really write Haskell this way - the obvious direct recursion is a lot more readable:

indexOf :: Char -> String -> Maybe Int
indexOf c = indexOf' 0
  where 
    indexOf' _ [] = Nothing
    indexOf' pos (h:t)
      | c == h = Just pos
      | otherwise = indexOf' (pos+1) t

edited Mar 5, 2016 at 22:26

answered Mar 5, 2016 at 22:17

Random Dev

52.4k9 gold badges95 silver badges120 bronze badges

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

4 Comments

Gilgamesz Over a year ago

Thanks a lot again. You said that I am mixing a currying and tuples. I cannot see it. If I understand correctly: In your example you used a currying. Am I right?

amalloy Over a year ago

y(\ ff c (h:t) pos -> ...)(c, l, 0) calls y with one argument, not three as you intend. (c, l, 0) is a three-tuple, remember.

chi Over a year ago

@Gilgamesz Carsten showed how to use tuples both in the lambda patterns and the arguments: y(\ff (ls, pos) -> ...)(ls, 0). You can also use a curried version simply removing tuples in both places: y(\ff ls pos -> ...) ls 0. Both are fine, but mixing the two approaches will cause a type mismatch.

Gilgamesz Over a year ago

@Carsten, I appreciated your piece of code. A lot of knowledge for me, as beginner!

Collectives™ on Stack Overflow

Haskell. Recursive Lambda. Errors

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related