4 Replies - 8511 Views - Last Post: 07 April 2011 - 09:26 PM

#1 mattlyons  Icon User is offline

  • D.I.C Regular

Reputation: 6
  • View blog
  • Posts: 301
  • Joined: 10-September 09

Compose a list of functions

Posted 05 April 2011 - 07:40 PM

The prof was pretty vague on what exactly is to be done but here are the instructions:

Quote

-Define 'composeList' which composes a list of functions.
-i.e.- composeList [f1, f2, ..., fn] x = (f1 . f2 . ... . fn) x == f1 (f2 ... (fn x)...))
-Give the type constructor of 'composeList' and explain why.
-Explain what would happen if 'composeList' had an empty parameter list.
-Hint: Write a function-level definition.


I am not even sure what the example means. Any help or tips?

Thanks for your time.

This post has been edited by mattlyons: 05 April 2011 - 07:41 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Compose a list of functions

#2 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 614
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Compose a list of functions

Posted 06 April 2011 - 08:52 AM

It sounds pretty cut and dry. He wants you to write a function called composeList that takes a list of functions and composes those functions.

Do you understand function composition in Haskell? If not, go take a look at Learn You a Haskell and read up about function composition. It should become clear.
Was This Post Helpful? 1
  • +
  • -

#3 mattlyons  Icon User is offline

  • D.I.C Regular

Reputation: 6
  • View blog
  • Posts: 301
  • Joined: 10-September 09

Re: Compose a list of functions

Posted 06 April 2011 - 06:39 PM

Thanks for the "Learn You a Haskell" read. It was pretty good but yet I still don't understand function composition well. I googled my question and came up with some answer that said this is what I was looking for:

composeList :: [a -> a] -> a -> a
composeList fs v = foldl (flip (.)) id fs $ v



But since I don't even understand the provided example from the professor, I don't even know how to test the above definition. What would be an example/output so that I could test if this works?

Then on top of all that, I don't even know how that definition works since I never learned what the dollar sign means.
Was This Post Helpful? 0
  • +
  • -

#4 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 614
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Compose a list of functions

Posted 07 April 2011 - 09:24 AM

In Haskell, functions are first class objects. They can be passed around just like any other value. You can pass around functions in the same way you'd pass around numbers or lists -- they're just regular ol' values.

Following this logic, you can store functions in a list.

Prelude> [(take 2), (drop 2)]

<interactive>:1:0:
    No instance for (Show ([a] -> [a]))
      arising from a use of `print' at <interactive>:1:0-19
    Possible fix: add an instance declaration for (Show ([a] -> [a]))
    In a stmt of an interactive GHCi command: print it



Ignore this error. Our example *did* work, the problem is that the REPL tried to print it, but doesn't know how to print it. We could fix this, but it isn't worth it here. Just keep in mind that the error is irrelevant.

These functions are partially applied. That means that we've applied take and drop to *some* of their arguments, but not all of them. For example, drop 2 is an entirely new function that takes the rest of drop's arguments which, in this case, is just one -- a list to drop from. The same applies to take.

So, we have our list of functions. Let's leave it for a moment and examine function composition.

Prelude> (take 2) . (drop 2)



We just composed these partially applied functions. This creates an entirely new function that takes the same number of arguments as the last function in the composition. This means that the new function created by the composition takes the same number of arguments as drop 2, which is just one. When we pass this new function it's argument, the last function in the composition is ran. This means that if we give this new function the argument [1,2,3,4,5,6], it'll pass that to our partially applied drop which will drop 2 elements from the front of the list. This, the result of drop, is passed to the next function in the composition which is our partially applied take. It results in a list of the first two elements in our list. This is our final result.

Calling this new function requires wrapping it in parentheses so that Haskell can tell where the function ends and begins:

Prelude> ((take 2) . (drop 2)) [1,2,3,4,5,6]
[3,4]



That's all there is to function composition. It's just a chain of functions.

Now, moving on to your problem. We need a function that takes a list of functions and composes them like we did above. We can do this recursively:

Prelude> let composeList [] = id; composeList (x:xs) = x . composeList xs
Prelude>  (composeList [(take 2), (drop 2)]) [1,2,3,4,5,6]
[3,4]



or we can do it with foldr:

Prelude> let composeList fs = foldr (.) id fs
Prelude>  (composeList [(take 2), (drop 2)]) [1,2,3,4,5,6]
[3,4]



In both cases, we're just iterating through the list, composing each new function with the last function, accumulating one big function made out of the compositions of the other functions. Notice how, as the base case, we use 'id'? This is a function that just returns it's argument. When the list becomes empty, the function will make one more composition and will compose id into the equation. This has no effect on the final function since it only returns it's argument.

Thus ends our function composition lesson. I hope this helped you out. I really encourage you to sit down and read Learn You a Haskell or Real World Haskell at every chance you get. It'll help you out in school.
Was This Post Helpful? 1
  • +
  • -

#5 mattlyons  Icon User is offline

  • D.I.C Regular

Reputation: 6
  • View blog
  • Posts: 301
  • Joined: 10-September 09

Re: Compose a list of functions

Posted 07 April 2011 - 09:26 PM

Thank you so much for the help. I will definitely be using Learn You a Haskell and will take a look at Real World Haskell as well. Thanks again for your haskell help Raynes :).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1