1

The task: I'm attempting to write a function with type signature minimum_recursive :: (a -> a -> Bool) -> [a] -> a . For its first parameter, it accepts a function I will call less that takes two parameters, and returns True if the first param is less than the second, False otherwise. minimum_recursive also accepts a list as its second parameter. Using explicit recursion, minimum_recursive should determine the smallest value in its input list [a].

My thinking: I was thinking to put the actual recursion in a helper function that also accepts an accumulator. I would call the helper function with the first item as the accumulator.

What I have so far: So far I have the following:

-- function as first parameter to min'
-- accepts two params, returns True if
-- first must come before second in sorted
-- order
less :: Ord a => a -> a -> Bool
less a b = a < b

-- Subpart B
minimum_recursive :: (a -> a -> Bool) -> [a] -> a
minimum_recursive func list = minimum_recursive_h func list []

I am having trouble figuring out how to even begin to write minimum_recursive_h.

Note: I know there probably is an easier way to accomplish this task, but I'm required to go about it as specified above.

Improve this question
3
  • 1
    If this is a homework question, you should tag it as such. Anyways, here's a pointer: base case is simple, now assume you already have a function that finds the minimal element in a list of length n - 1, how would you combine it with the current element to get an answer for a list of length n? Commented Apr 11, 2012 at 17:37
  • I guess I would find the minimal element of list of length n - 1, then compare this to the original list's element n? I don't know the Haskell syntax for this. I'll do some research. Commented Apr 11, 2012 at 17:44
  • 1
    See also the source of minimumBy from the standard libraries. Commented Apr 11, 2012 at 18:45

3 Answers 3

Reset to default
2

You could do it like this:

minimum_recursive _ [] = error "no minimum of empty list"
minimum_recursive _ [x] = x
minimum_recursive f (x:xs) = let m = minimum_recursive f xs
                             in if f x m then x else m

Or, with an accumulator:

minimum_recursive _ [] = error "no minimum of empty list"
minimum_recursive f (x:xs) = helper f x xs
    where
      helper _ m [] = m
      helper f m (x:xs) 
          | f m x = helper f m xs
          | otherwise = helper f x xs
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Really like the accumulator solution. Any reason why when using the less function in my question, and when I do my main with an empty list like so: main :: IO () main = print $ minimum_recursive less [] I get this error Ambiguous type variable "a0" in the constraints: (Show a0) arising from a use of "print" at hello.hs:27:8-12 (Ord a0) arising from a use of "less" at hello.hs:27:34-37
@gonzoc0ding: The problem is that you never constrain the type of list's elements. [] is valid list for any type. In this case, GHC cannot automagically pick the "right" type for you. If you want, you can give an explicit type, such as minimum_recursive less ([] :: [Integer]).
what's the downvote for? I'd prefer to do this using a fold (or really minumumBy, but the poster said he required explicit recursion for some reason.
1

If you want the smallest ellement in the list I sugest that you add the smallest ellement you currently have as a parameter to the function.

minimum_recursive :: (a -> a -> Bool) -> a -> [a] -> a
minimum_recursive f min [] = min
minimum_recursive f min (x:xs) | f min x   = minimum_recursive f min xs
                               | otherwise = minimum_recursive f x   xs

You should also change the type in the function that call this from a to Maybe a since there are no smallest ellement in an empty list. Here some help about Maybe

If you want to do it without an extra parameter you could store the smallest ellement in the beginning of the list ass well. In this case it's important to use Maybe 

minimum_recursive :: (a -> a -> Bool) -> [a] ->Maybe a
minimum_recursive f [] = Nothing
minimum_recursive f (x:[]) = Just x
minimum_recursive f (y:(x:xs)) | f y x     = minimum_recursive f (y:xs)
                               | otherwise = minimum_recursive f (x:xs)

This is how the minumum can be found ehit fold. Look at the beauty of functionall programming. But this wont work for the empty list

simplefold :: [a] -> a
simplefold (x:xs) = foldl min x xs

But we can embed this function in one that checks if the list is empty and return Nothing in that case.

betterfold :: [a] -> Maybe a
betterfold [] = Nothing
beterfold l   = Just (simplefold l)
Improve this answer

5 Comments

Nice suggestion about Maybe, but this problem can be solved without adding a parameter to minimum_recursive.
What if I wanted to use a foldl1 instead of explicit recursion? Any suggestions?
added how to fold to the answer
Awesome. One thing I'm trying to do, is make the simple fold have the same type signature as minimum_recursive, e.g., take the less function as a parameter and use it in the computation
replace the min with the function you have as parameter
1

The classic way to solve problems recursively is the following:

  1. Assume you've nearly solved the problem, except for the final step.
  2. Write the code that, given the solution for all except that final step, computes the solution produced by that final step.
  3. Write the base case.

In the case of lists, this translates to this pattern:

  1. Base case: what should the solution be for []? (if anything; in the case of your minimum_recursive function, this would be an error).
  2. For a nonempty list x:xs, assume you already have almostTheResult = minimum_recursive f xs. How do you compute minimum_recursive (x:xs) given that?

I'll give you a big hint: your minimum_recursive can be implemented in terms of foldr and this function:

minBy :: (a -> a -> Bool) -> a -> a -> a
minBy pred x y = if pred x y then x else y

The foldr function does exactly what I'm describing above. The first argument to foldr is the function that computes the final solution given the list head and the partial solution for the tail, and the second argument is the result base case.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.