(a -> [b]) -> [a -> b] ?

Joachim Breitner

4 Dec 2006 4 Dec '06

2 p.m.

Hi, while pondering over the four fours problem, I wondered: Is there a function of type (a -> [b]) -> [a -> b] It looks a bit like sequence when applied in the ((->) a) Monad: sequence :: [a -> b] -> a -> [b] but I was looking for the other direction. I came up with: \g -> map (\n a -> g a !! n) [1..] which has the desired type and functionality, but it looks rather inelegant and messy. Any better ideas? Thanks, Joachim -- Joachim "nomeata" Breitner mail: mail@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: joachimbreitner@amessage.de | http://www.joachim-breitner.de/ Debian Developer: nomeata@debian.org

Show replies by date

Taral

4 Dec 4 Dec

2:05 p.m.

On 12/4/06, Joachim Breitner wrote:

...

\g -> map (\n a -> g a !! n) [1..]

I think that's about as good as it gets. -- Taral "You can't prove anything." -- Gödel's Incompetence Theorem

Nicolas Frisby

2:12 p.m.

It seems there's an assumption about the range of the parameter function and the range of the entire function. That is, I think we're assuming that the length of the final result is the same as the length of the result of the first function? If I'm correct in presuming that constraint, then I think this indicates that a "more elegant" solution might involve using the lightweight-dependently-typed vectors approach. Though I can't promise it will actually be nicer! Nick On 12/4/06, Joachim Breitner wrote:

...

Hi,

while pondering over the four fours problem, I wondered: Is there a function of type (a -> [b]) -> [a -> b]

It looks a bit like sequence when applied in the ((->) a) Monad: sequence :: [a -> b] -> a -> [b] but I was looking for the other direction.

I came up with: \g -> map (\n a -> g a !! n) [1..] which has the desired type and functionality, but it looks rather inelegant and messy. Any better ideas?

Thanks, Joachim

-- Joachim "nomeata" Breitner mail: mail@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: joachimbreitner@amessage.de | http://www.joachim-breitner.de/ Debian Developer: nomeata@debian.org _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Joachim Breitner

2:24 p.m.

Hi, Am Montag, den 04.12.2006, 13:12 -0600 schrieb Nicolas Frisby:

...

It seems there's an assumption about the range of the parameter function and the range of the entire function. That is, I think we're assuming that the length of the final result is the same as the length of the result of the first function?

Ah, of course, I forgot to mention to say what the function should do :-) If we call in unsequence, the following should be true for f::(a -> [b]) and v::a f v == map (\g -> g v) (unsequence f) Let’s see if I can prove that my suggested solution is correct: f v == map (\g -> g v) (map (\n a -> f a !! n) [1..]) == map ((\g -> g v) . (\n a -> f a !! n)) [1..] == map ((\n -> (f v !! n)) [1..] * here I use that map (\n -> l !!n ) [1..] == l. I hope that is valid == f v Ok, looks good. But still, I don’t like this solution with (!!) for some reason. Thanks, Joachim

...

On 12/4/06, Joachim Breitner wrote:

...
Hi,

while pondering over the four fours problem, I wondered: Is there a function of type (a -> [b]) -> [a -> b]

It looks a bit like sequence when applied in the ((->) a) Monad: sequence :: [a -> b] -> a -> [b] but I was looking for the other direction.

I came up with: \g -> map (\n a -> g a !! n) [1..] which has the desired type and functionality, but it looks rather inelegant and messy. Any better ideas?

Thanks, Joachim

-- Joachim "nomeata" Breitner mail: mail@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: joachimbreitner@amessage.de | http://www.joachim-breitner.de/ Debian Developer: nomeata@debian.org _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Joachim "nomeata" Breitner mail: mail@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: joachimbreitner@amessage.de | http://www.joachim-breitner.de/ Debian Developer: nomeata@debian.org

Matthew Brecknell

2:59 p.m.

Joachim Breitner:

...

here I use that map (\n -> l !!n ) [1..] == l. I hope that is valid

map (\n -> l !! n) [1..] is more like (tail l). Did you mean to use [0..]?

Joachim Breitner

4:02 p.m.

Hi, Am Dienstag, den 05.12.2006, 05:59 +1000 schrieb Matthew Brecknell:

...

Joachim Breitner:

...
here I use that map (\n -> l !!n ) [1..] == l. I hope that is valid

map (\n -> l !! n) [1..] is more like (tail l). Did you mean to use [0..]?

Probably. I hardly use (!!), so I did not remember if it starts with 0 or 1. Thanks for the hint, Joachim -- Joachim Breitner e-Mail: mail@joachim-breitner.de Homepage: http://www.joachim-breitner.de ICQ#: 74513189

David Roundy

2:37 p.m.

On Mon, Dec 04, 2006 at 07:00:23PM +0000, Joachim Breitner wrote:

...

I came up with: \g -> map (\n a -> g a !! n) [1..] which has the desired type and functionality, but it looks rather inelegant and messy. Any better ideas?

I like sequence a2bs = (head . a2bs) : sequence (tail . a2bs) This also makes it explicit that by golly your function had better return an infinite list, or we're in trouble. -- David Roundy Department of Physics Oregon State University

apfelmus＠quantentunnel.de

6 Dec 6 Dec

6:28 a.m.

...

while pondering over the four fours problem, I wondered: Is there a function of type (a -> [b]) -> [a -> b]

It looks a bit like sequence when applied in the ((->) a) Monad: sequence :: [a -> b] -> a -> [b] but I was looking for the other direction.

I came up with: \g -> map (\n a -> g a !! n) [1..] which has the desired type and functionality, but it looks rather inelegant and messy. Any better ideas?

While you showed that there exists unsequence :: (a -> [b]) -> [a -> b] , I doubt that it's very useful. The point is that (sequence) is not surjective: (a -> [b]) has strictly more functions than [a -> b]. (a -> [b]) has the freedom to adjust the length of the resulting depending on a list whereas [a -> b] hasn't. (sequence) converts an Applicative Functor to a Monad but there is no canonical other way round. In other words, unsequence . sequence === id but sequence . unsequence =/= id Regards, apfelmus

6740

Age (days ago)

6742

Last active (days ago)

List overview

Download

7 comments

6 participants

participants (6)

apfelmus＠quantentunnel.de
David Roundy
Joachim Breitner
Matthew Brecknell
Nicolas Frisby
Taral

(a -> [b]) -> [a -> b] ?

Joachim Breitner

Taral

Nicolas Frisby

Joachim Breitner

Matthew Brecknell

Joachim Breitner

David Roundy

apfelmus＠quantentunnel.de

tags

participants (6)