CODEWITHSUNDEEP
haskellfunctional-programming
EasternDude
EasternDude

Reputation: 423

How do i use recursive function in haskell to find nth element of a list? and more

i've started studying functional programming in Haskell recently and was given some problems to solve, it asks to make your own versions of some system function for lists using recursion and basic system functions. the functions i need to write is:

I started with the first one and wrote a definition like this:

nthelement :: Eq a => [a] -> a -> a

in imperative language i would make a counter variable (say i) and use system function tail to remove first element of list until i = n. But as I learned that in functional you can only do constants I can't think of a way to decide when to stop recurring and return the element rather then recuring tail function till the list is empty.

Please help me to figure this out. Any help on doing first function or any of them would be very nice. Thanks.

Upvotes: 3

Views: 2237

Answers (2)

Erik Kaplun
Erik Kaplun

Reputation: 38247

I'm only providing a general answer here to one of the questions you raised. I'm hoping this will help you understand the general problem better and come up with solutions to your specific problems/tasks.

in imperative language i would make a counter variable (say i) and use system function tail to remove first element of list until i = n. But as I learned that in functional you can only do constants I can't think of a way to decide when to stop recurring and return the element rather then recuring tail function till the list is empty.

you can always "simulate" a for loop with a state variable and breaking out of the loop using recursion:

Python:

def foo(xs):
    state = initial_state
    for x in xs:
        state = make_new_state(x, state)
        if not condition(state, x):
            break
    return state

in the equivalent Haskell code, you would use an inner function with an extra argument for the state. You can also expose the extra argument on foo but normally you don't want to expose that to the callers of foo:

foo xs = go initialState xs
  where go []     state = state
        go (x:xs) state = if not (condition state x)
                          then state
                          else go xs (makeNewState x state)

for many algorithms, breaking out of the loop is not needed at all, in which case the "pattern" becomes:

foo xs = go initialState xs
  where go []     state = state
        go (x:xs) state = go xs (makeNewState x state)

where makeNewState is the logic you execute at each step (and it doesn't have to be in a separate function, of course).

For the latter case, there are some generic functions foldr and foldl and foldl', such that:

foo xs = foldr makeNewState initialState xs

Furthermore: there are also things like the State monad, which let you write imperative logic in a pure manner, but it's best to understand things like "raw" recursion and folds first, and only then move on to things like monads and explicit state.

Upvotes: 1

C. Quilley
C. Quilley

Reputation: 1059

(As @Bergi correctly notes in the comments, you should check that your signature and the one of !! in the standard libraries coincide!)

Instead of thinking of the i in list !! i as a variable, think of it as a function parameter. Then, consider the different cases of this parameter, and decide what your !! function should do in each case. Then, think about what options your list parameter list has, and how you should consider them:

Expanding all the potential options for i and list gives us the following:

nthelement :: [a] -> Integer -> a
nthelement [] 0 = -- ?
nthelement [] i = -- ?
nthelement (l:ls) 0 = -- ?
nthelement (l:ls) n = -- ?

The remaining functions can be written by following a similar strategy.

Upvotes: 9

Related Questions