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

3
votes

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:

  • !! (nth item in a list)
  • append (joining lists together)
  • subst (substitution) e.g. subst 'x' 'y' ['q','x','r','x','s'] ~> ['q','y','r','x','y','s']
  • intersection e.g. intersection [2,5,7] [9,7,3,5] ~> [5,7]
  • union union e.g union [2,5,7] [9,7,3,5] ~> [2,5,7,9,3]
  • reverse e.g. reverse [4,5,6,7] ~> [7,6,5,4]

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.

2
haskellfunctional-programming
First start with an accurate type signature. nthelement does not need Eq a, and it doesn't take an a next to the list. Example use would be nthelement ['a','c','b'] 1 ~> 'c' – Bergi
Try with pattern matching and standard structural recursion. Do not use head or tail. – Bergi
i've mant to write Ord a. As i understand it: Ord a => means that arguments to this function must be of ordered type (Int's , Float's but not Strings?) [a] -> a -> a means that function will take one list argument , one (Int/Float) and will return Int/Float (Ord) nthelement [1,2,3] 1 would return 2 Am i wrong here? – EasternDude
Actually it is xs <<!!>> n = head . drop n $ xs – Lol4t0
@EasternDude: No, Ord a means that as are comparable - <, ==, >. What you meant is a Num (arithmetic operations). What you actually need is an integral type, such as Integer or Int. And the basic problem you had that you've specified the index to be of the same type as the list elements. – Bergi

2 Answers

9
votes

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

1
votes

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.