defining mapPairs function
|
View:
New views
12 Messages
—
Rating Filter:
Alert me
|
 |
defining mapPairs function
by Alexteslin
::
Rate this Message:
Hello,
I just came across with this question on the exam and can not think of implementing it. mapPair :: (a -> a -> a) -> [a] -> [a] such that mapPairs f [x1, x2, x3, x4...] = [f x1 x2, f x3 x4,...] and if the list contains an odd number of elements, the last one is kept unchanged, for example mapPairs f [x1, x2, x3] = [f x1 x2, x3] Any ideas will be appreciated, thanks |
|
|
Re: defining mapPairs function
by Alexteslin
::
Rate this Message:
Oh, I think i just defined it - seems to work. I spent some time on the exam and made silly mistakes: mapPairs :: (a -> a -> a) -> [a] -> [a] mapPairs f [x] = [x] mapPairs f [] = [] mapPairs f (x:xs) = f x (head xs) : mapPairs f (tail xs) I was concing f x to (head xs) as well and mapPairs f [x] = x - this is very silly mistake. Does anyone think this is the right answer? |
|
|
Re: defining mapPairs function
by ndmitchell
::
Rate this Message:
Hi Alexteslin,
> I just came across with this question on the exam and can not think of > implementing it. > > mapPair :: (a -> a -> a) -> [a] -> [a] > > such that mapPairs f [x1, x2, x3, x4...] = [f x1 x2, f x3 x4,...] I would implement this using direct recursion. As a starting point, the standard definition of map is: map f [] = [] map f (x:xs) = f x : map f xs You should be able to start at this and modify it to give the behaviour you require. If you want further hints, you might want to try the Haskell IRC Channel, which is good for these kind of questions. http://www.haskell.org/haskellwiki/IRC_channel Thanks Neil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: defining mapPairs function
by ndmitchell
::
Rate this Message:
Hi
> mapPairs :: (a -> a -> a) -> [a] -> [a] > mapPairs f [x] = [x] > mapPairs f [] = [] > mapPairs f (x:xs) = f x (head xs) : mapPairs f (tail xs) It looks like it works, but you can get a better version by changing the last line: mapPairs f (x:y:zs) = ... - left as an exercise, but no need for head or tail. Thanks Neil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: defining mapPairs function
by Brent Yorgey
::
Rate this Message:
On 8/29/07, Alexteslin <alexteslin@...> wrote:
Wait, is this an exam for a class you're taking? Or just a problem from an exam that you're trying to solve for fun? If the former, it really isn't appropriate to ask the list to solve the problem for you, or even for hints. Your work on the exam should be your own. -Brent _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: defining mapPairs function
by Dan Weston
::
Rate this Message:
Sometimes it is interesting to approach things from a different
perspective. The goofyness below will have been useful if it interests you in point-free programming. And anyway, I sure had a good time writing it... I am composing several common Haskell idioms: 1) When adjacent list elements are paired is (duplicate,offset one of them, zip together): Prelude> let z = [2,3,5] in zipWith (*) z (tail z) [6,15] 2) Uninterleaving (slicing) a list: Prelude> let slice = fst . foldr (\a ~(x,y) -> (a:y,x)) ([],[]) Prelude> slice [1..10] [1,3,5,7,9] For fun, I will do the slicing by changing the odd-indexed elements to Just x, and the even ones to Nothing, then filter only the Justed elements. There is a twist in your problem: do something special with the last odd (orphaned) element, i.e. append it. One thing to watch out for is that functions like head, tail, last are partial functions that don't play well with the empty list. In my case, I forstall disaster by prepending an unused Nothing value to my list before calling last. For comparison with your concise solution, below is my much more obfuscated one. Believe it or not, this algorithm was the first one that popped into my head. I have encoded it in point-free notation so that it reads along with its algorithm description (and because it's so much fun!) If the use of &&& and >>> is new to you, just read through to get a taste of how it can be used. Note that there is no variable name anywhere in the code, only functions! Solving the same problem several different ways will help build your toolbox. I am not recommending my solution for your exam (it's longer and less efficient than yours), only pointing out that there is always more than one way to do something in Haskell. :) import Control.Arrow((&&&),(>>>)) import Data.Maybe(catMaybes,maybeToList) mapPair = (id &&& tail >>> -- offset list by one uncurry (zipWith (*)) >>> -- multiply adjacent alternate >>> -- mark even elements catMaybes) -- delete even elements &&& -- Tuple this up with... (alternate >>> -- keep odd indices (Nothing:) >>> -- make sure there is a last last >>> -- get last maybeToList) -- keep if it had odd index >>> -- and then... uncurry (++) -- append pair of lists where alternate = zipWith ($) (cycle [Just,const Nothing]) -- Mark even-indexed elements for deletion -- cycle goes on forever, but zipWith stops at -- the end of the shorter list, so no worries. In this formulation, you can see that the whole second half above is there just to handle the orphaned last element, suggesting that there is something unnatural in the problem specification (probably put there to keep you from just using zipWith!). Here is a worked example for [2,3,5,7,11] in case you're not used to point-free programming: (id &&& tail >>> -- ([2,3,5,7,11],[3,5,7,11]) uncurry (zipWith (*)) >>> -- [6,15,35,77] alternate >>> -- [Just 6,Nothing,Just 35,Nothing] catMaybes) -- [6,35] &&& (alternate >>> -- [Just 2,Nothing,Just 5,Nothing,Just 11] (Nothing:) >>> -- [Nothing,Just 2,Nothing,Just 5, -- Nothing,Just 11] last >>> -- Just 11 maybeToList) -- [11] >>> -- ([6,35],[11]) uncurry (++) -- [6,35,11] Dan Weston Alexteslin wrote: > > > Alexteslin wrote: >> Hello, >> >> I just came across with this question on the exam and can not think of >> implementing it. >> >> mapPair :: (a -> a -> a) -> [a] -> [a] >> >> such that mapPairs f [x1, x2, x3, x4...] = [f x1 x2, f x3 x4,...] >> >> and if the list contains an odd number of elements, the last one is kept >> unchanged, for example >> >> mapPairs f [x1, x2, x3] = [f x1 x2, x3] >> >> >> Any ideas will be appreciated, thanks >> > > Oh, I think i just defined it - seems to work. > I spent some time on the exam and made silly mistakes: > > mapPairs :: (a -> a -> a) -> [a] -> [a] > mapPairs f [x] = [x] > mapPairs f [] = [] > mapPairs f (x:xs) = f x (head xs) : mapPairs f (tail xs) > > I was concing f x to (head xs) as well and > mapPairs f [x] = x - this is very silly mistake. > > Does anyone think this is the right answer? > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: defining mapPairs function
by Max Vasin-2
::
Rate this Message:
2007/8/30, Neil Mitchell <ndmitchell@...>:
> Hi > > > mapPairs :: (a -> a -> a) -> [a] -> [a] > > mapPairs f [x] = [x] > > mapPairs f [] = [] > > mapPairs f (x:xs) = f x (head xs) : mapPairs f (tail xs) > > It looks like it works, but you can get a better version by changing > the last line: > > mapPairs f (x:y:zs) = ... - left as an exercise, but no need for head or tail. And you can get less equations if you replace first two equations with mapPairs f x = x and place it after Neil's. -- WBR, Max Vasin JID: maxvasin@... _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: defining mapPairs function
by Devin Mullins
::
Rate this Message:
That's great (really, thank you for such a fun example of Arrow
programming), but isn't the (*) on line two of mapPair supposed to be a "point"? How would you make a point-less version of mapPair that actually had the type signature (a->a->a)->[a]->[a]*? (For that matter, /would/ you?) Devin * Grr, you're right. Were it not for that odd requirement, the type could be loosened to (a->a->b)->[a]->[b]. Maybe mapPairs should take a monadic (that is, one-arg) function to handle the dangling oddies. Dan Weston wrote: > import Control.Arrow((&&&),(>>>)) > import Data.Maybe(catMaybes,maybeToList) > > mapPair = (id &&& tail >>> -- offset list by one > uncurry (zipWith (*)) >>> -- multiply adjacent > alternate >>> -- mark even elements > catMaybes) -- delete even elements > > &&& -- Tuple this up with... > > (alternate >>> -- keep odd indices > (Nothing:) >>> -- make sure there is a last > last >>> -- get last > maybeToList) -- keep if it had odd index > > >>> -- and then... > > uncurry (++) -- append pair of lists > > where alternate = zipWith ($) (cycle [Just,const Nothing]) > -- Mark even-indexed elements for deletion > -- cycle goes on forever, but zipWith stops at > -- the end of the shorter list, so no worries. Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: defining mapPairs function
by Dan Weston
::
Rate this Message:
That's just a minor change of plumbing:
import Control.Arrow((***),(&&&),(>>>),app) import Data.Maybe(catMaybes,maybeToList) mapPair :: (a -> a -> a) -> [a] -> [a] mapPair = curry mp where mp = (((zipWith >>> uncurry) *** -- (inter-elem function (id &&& tail) >>> -- ,duplicate and offset) app >>> -- apply fst to snd alternate >>> -- mark even elements catMaybes)) -- delete even elements &&& -- Tuple this up with... (snd >>> alternate >>> -- keep odd indices (Nothing:) >>> -- make sure there is a last last >>> -- get last maybeToList) -- keep if it had odd index >>> -- and then... uncurry (++) -- append pair of lists alternate = zipWith ($) (cycle [Just,const Nothing]) -- Mark even-indexed elements for deletion -- cycle goes on forever, but zipWith stops at -- the end of the shorter list, so no worries. When you find yourself manually plumbing the inputs, that's probably where point-free has morphed into point-less programming! I plead guilty! :) Dan Weston Devin Mullins wrote: > That's great (really, thank you for such a fun example of Arrow > programming), but isn't the (*) on line two of mapPair supposed to be a > "point"? How would you make a point-less version of mapPair that > actually had the type signature (a->a->a)->[a]->[a]*? (For that matter, > /would/ you?) > > Devin > * Grr, you're right. Were it not for that odd requirement, the type > could be loosened to (a->a->b)->[a]->[b]. Maybe mapPairs should take a > monadic (that is, one-arg) function to handle the dangling oddies. > > Dan Weston wrote: >> import Control.Arrow((&&&),(>>>)) >> import Data.Maybe(catMaybes,maybeToList) >> >> mapPair = (id &&& tail >>> -- offset list by one >> uncurry (zipWith (*)) >>> -- multiply adjacent >> alternate >>> -- mark even elements >> catMaybes) -- delete even elements >> >> &&& -- Tuple this up with... >> >> (alternate >>> -- keep odd indices >> (Nothing:) >>> -- make sure there is a last >> last >>> -- get last >> maybeToList) -- keep if it had odd index >> >> >>> -- and then... >> >> uncurry (++) -- append pair of lists >> >> where alternate = zipWith ($) (cycle [Just,const Nothing]) >> -- Mark even-indexed elements for deletion >> -- cycle goes on forever, but zipWith stops at >> -- the end of the shorter list, so no worries. > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@... > http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: defining mapPairs function
by Alexteslin
::
Rate this Message:
Hi, It is the former, but I sat an exam and trying to discuss my exam answers which will make no difference to what so ever to an exam, as an exam duration was 1.5 hours. Which means that no matter how much i would like to try to amend my answers, it is too late. I merely trying to figure out if i answered my questions right. |
|
|
Re: defining mapPairs function
by Ross Paterson
::
Rate this Message:
On Sat, Sep 01, 2007 at 04:59:50AM -0700, Alexteslin wrote:
> It is the former, but I sat an exam and trying to discuss my exam answers > which will make no difference to what so ever to an exam, as an exam > duration was 1.5 hours. Which means that no matter how much i would like to > try to amend my answers, it is too late. I merely trying to figure out if i > answered my questions right. I can confirm that this is innocent checking after the fact. This is question 2(e) on my resit paper, but the first posting was half an hour after the end of the exam. The answer you posted is correct, though those suggested by Neil and Max would be neater. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: defining mapPairs function
by Brent Yorgey
::
Rate this Message:
On 9/1/07, Alexteslin <alexteslin@...> wrote:
OK, my apologies! From the way you phrased it, it sounded to me like it was some sort of take-home exam you were working on. In retrospect I guess that was sort of unlikely, but stranger things have happened. =) -Brent _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
| Free embeddable forum powered by Nabble | Forum Help |
