Tuesday, June 19, 2007

Fun with Functions

Pete Nuttall writes about the fnreduce function:

fnreduce :: [(a->a)]->a->a
fnreduce [] value = value
fnreduce (a:as) value = freduce as $ a value

A shorter, although not necessarily clearer, expression of this function would be

fnreduce as value = (foldr (flip (.)) id as) value

This just says that to apply a list of functions to a value, we first compose all the functions by folding down the list, then apply the result to the value. The important thing here is (flip (.)), which says to compose backwards; it means that fnreduce [f, g, h] returns (h . g . f . id) instead of (f . g . h . id). An interesting side note is that it doesn't matter (from a semantic point of view) whether I use foldl or foldr, since function composition is associative:

f . (g . (h . id)) = ((id . f) . g) . h

But "flip" here feels a little confusing. A clearer approach would be to reverse the list instead of reversing the operator:

fnreduce as value = foldr (.) id (reverse as) value

This might be less efficient, but it says in a much clearer way what I'm doing.

Yet another option is to eschew the use of function composition:

fnreduce as value = foldl (flip ($)) value as

Here ($) is the application function; (f$x) applies f to x. So if we reverse it (call this $$), we get (x$$f) applies f to x. Folding this from the left down the list [f, g, h] gives us (((value$$f)$$g)$$h), which is exactly what the original fnreduce did.

I think this is maybe the best fold-based solution to the original problem, because it models what's happening (repeatedly transforming a value with a series of functions) directly. To use a right-fold, you have to remove the flip and reverse as (the reason this is necessary is left as an exercise to the reader).

Pete also asks whether this can be done for heterogenous lists in a type-safe manner. The core problem is, what is the type of our list? It can't actually be a list: in order to check that it's OK to combine the output of one function with the input of another, we would need the elements of the list to have different types. You can't do this in Haskell, even a crazy ghc-extended Haskell.

So, we could try something like this:

module Test where

data TransformList a b where
Nil :: TransformList a a
Cons :: (a -> b) -> TransformList b c -> TransformList a c

apply :: TransformList a b -> a -> b
apply Nil = id
apply (Cons f fs) = (apply fs) . f

This lets us do stuff like

> apply (Cons (\x -> x + 1) (Cons (\x -> show x) Nil)) 5

This is cute, but I don't know that it's really that useful. After all, how is it any better than the following?

> ((\x -> show x) . (\x -> x + 1)) 5

Everything the above code lets you do with TransformList could just as well be done with the humble compose operator. The only benefit would be if we could somehow do "list-like" stuff with a transform list. For instance, say we want to write the following function:

traceIntermediates Nil x = (x, [])
traceIntermediates (Cons f l) x = let x' = f x
(x'', ss) = traceIntermediates l x'
(x'', (show x'):ss)

This won't compile, because we don't know that x' is a member of the Show typeclass. And there is no way to fix this in a reusable way using any technique that relies on building a type parameterized on the input and output types: the problem is that we need to say something about the types of the intermediate values, but their type variables are inaccessible.

In other words, there isn't any way to write down a constraint on the type "TransformList a b" that constrains the intermediates. So I've just wasted a lot of typing duplicating the compose operator. Yay.

On the other hand, it's entirely possible to do this if you don't mind some boilerplate code.

data ShowTransformList a b where
Nil :: (Show a) => ShowTransformList a a
Cons :: (Show a, Show b, Show c) => (a -> b) -> ShowTransformList b c -> ShowTransformList a c

traceIntermediates :: ShowTransformList a b -> a -> (b, [String])
traceIntermediates Nil x = (x, [])
traceIntermediates (Cons f l) x = let x' = f x
(x'', ss) = traceIntermediates l x'
(x'', (show x'):ss)

apply :: ShowTransformList a b -> a -> b
apply Nil = id
apply (Cons f fs) = (apply fs) . f

Now I can do this:

> traceIntermediates
(Cons (\x -> x + 1)
(Cons (\x -> x * 2)
(Cons (\x -> x - 5)
(Cons show
(Cons (read :: String -> Double)
Nil))))) 5


At 12:51 AM, Blogger oakleyses said...

kate spade handbags, prada outlet, nike air max, louis vuitton, nike air max, louis vuitton outlet online, burberry outlet online, burberry outlet online, tiffany and co jewelry, michael kors outlet, gucci handbags, tory burch outlet, louis vuitton outlet, chanel handbags, jordan shoes, longchamp outlet online, nike shoes, louboutin shoes, red bottom shoes, coach outlet store online, kate spade outlet online, polo ralph lauren outlet, oakley vault, coach outlet, prada handbags, coach purses, louis vuitton handbags, longchamp handbags, christian louboutin outlet, oakley sunglasses, cheap oakley sunglasses, michael kors outlet online, michael kors outlet online, louis vuitton outlet, polo ralph lauren, christian louboutin shoes, michael kors outlet online, ray ban outlet, nike free, longchamp outlet, michael kors outlet store, michael kors outlet online, coach outlet, true religion, ray ban sunglasses

At 12:51 AM, Blogger oakleyses said...

abercrombie and fitch, longchamp pas cher, north face, vans pas cher, nike free, nike air max, longchamp, tn pas cher, hollister, air max pas cher, michael kors canada, chaussure louboutin, oakley pas cher, sac vanessa bruno, ray ban uk, louis vuitton uk, hollister, new balance pas cher, lululemon, nike free pas cher, north face pas cher, scarpe hogan, nike trainers, air max, nike roshe, ralph lauren pas cher, barbour, nike huarache, burberry pas cher, guess pas cher, nike air max, true religion outlet, longchamp, lacoste pas cher, sac michael kors, ralph lauren, louis vuitton pas cher, michael kors uk, nike blazer pas cher, mulberry, nike air force, air jordan, hermes pas cher, louis vuitton, nike roshe run, timberland, sac louis vuitton, ray ban pas cher, converse pas cher, true religion outlet

At 12:52 AM, Blogger oakleyses said...

herve leger, soccer jerseys, uggs outlet, jimmy choo shoes, lululemon outlet, nfl jerseys, canada goose pas cher, vans outlet, soccer shoes, roshe run, valentino shoes, moncler, rolex watches, chi flat iron, uggs on sale, canada goose, north face outlet, ghd, new balance outlet, north face jackets, mcm handbags, ugg soldes, moncler, canada goose uk, mont blanc pens, beats headphones, canada goose outlet, celine handbags, instyler ionic styler, ferragamo shoes, ugg boots, bottega veneta, ugg, moncler outlet, abercrombie and fitch, ugg outlet, wedding dresses, mac cosmetics, birkin bag, reebok outlet, canada goose outlet, insanity workout, moncler, giuseppe zanotti, asics shoes, hollister, canada goose outlet, babyliss pro, marc jacobs outlet, p90x workout

At 8:04 PM, Blogger xjd7410@gmail.com said...

20151014 junda
Louis Vuitton Handbags Factory Store
Louis Vuitton Bags On Sale
Louis Vuitton Bags Outlet Store
cheap ugg boots
louis vuitton outlet
Michael Kors Outlet Real Handbags Online
ugg boots
Air Jordan 3 III Retro Free Shipping
louis vuitton outlet
Christian Louis Vuitton Red Bottoms
coach factory outlet
ray ban sunglasses uk
Ugg Boots,Ugg Boots Outlet,Ugg Outlet,Cheap Uggs,Uggs On Sale,Ugg Boots Clearance,Uggs For Women
Coach Outlet Store Online Handbags Clearance
canada goose outlet
ugg boots outlet
Abercrombie And Fitch Kids Online
true religion outlet
cheap jordan shoes
New Louis Vuitton Handbags Outlet
cheap uggs
nfl jerseys
canada goose jackets
Abercrombie and Fitch Outlet Sale
louis vuitton outlet
canada goose outlet
uggs australia
michael kors outlet stores
Coach Factory Outlet Online Sale

At 8:26 PM, Blogger oakleyses said...

uggs outlet, uggs on sale, ray ban sunglasses, ray ban sunglasses, louis vuitton, michael kors outlet online, oakley sunglasses wholesale, christian louboutin outlet, louis vuitton, uggs outlet, louis vuitton outlet, polo outlet, prada handbags, nike free, chanel handbags, longchamp outlet, michael kors outlet, replica watches, louis vuitton outlet, oakley sunglasses, michael kors outlet online, prada outlet, michael kors outlet online, longchamp outlet, burberry handbags, michael kors outlet, kate spade outlet, ray ban sunglasses, longchamp outlet, louis vuitton outlet, oakley sunglasses, nike air max, oakley sunglasses, replica watches, ugg boots, polo ralph lauren outlet online, ugg boots, gucci handbags, jordan shoes, cheap oakley sunglasses, michael kors outlet online, christian louboutin uk, burberry outlet, tory burch outlet, tiffany and co, christian louboutin shoes

At 8:27 PM, Blogger oakleyses said...

michael kors, nike tn, ralph lauren uk, abercrombie and fitch uk, north face uk, ray ban pas cher, nike free uk, lululemon canada, michael kors, true religion jeans, coach outlet, coach outlet store online, hollister uk, sac longchamp pas cher, vans pas cher, nike blazer pas cher, louboutin pas cher, nike air max uk, michael kors pas cher, nike free run, nike air max uk, new balance, sac hermes, jordan pas cher, true religion outlet, replica handbags, nike roshe, longchamp pas cher, guess pas cher, true religion outlet, north face, polo ralph lauren, coach purses, hollister pas cher, oakley pas cher, timberland pas cher, air max, polo lacoste, nike air force, nike roshe run uk, burberry pas cher, converse pas cher, nike air max, sac vanessa bruno, mulberry uk, hogan outlet, michael kors outlet, true religion outlet, ray ban uk, kate spade

At 8:32 PM, Blogger oakleyses said...

beats by dre, nfl jerseys, nike trainers uk, mcm handbags, lululemon, reebok outlet, valentino shoes, wedding dresses, nike roshe run, celine handbags, ghd hair, ferragamo shoes, mont blanc pens, louboutin, giuseppe zanotti outlet, new balance shoes, timberland boots, oakley, soccer shoes, nike air max, iphone 5s cases, nike huaraches, iphone 6 plus cases, herve leger, iphone 6s plus cases, p90x workout, babyliss, vans outlet, north face outlet, iphone cases, jimmy choo outlet, iphone 6 cases, s6 case, abercrombie and fitch, bottega veneta, north face outlet, hermes belt, longchamp uk, ralph lauren, chi flat iron, insanity workout, iphone 6s cases, ipad cases, baseball bats, mac cosmetics, instyler, hollister, soccer jerseys, asics running shoes, hollister clothing

At 8:33 PM, Blogger oakleyses said...

doudoune moncler, pandora uk, moncler outlet, vans, converse outlet, montre pas cher, louis vuitton, moncler, moncler, canada goose, canada goose outlet, ugg uk, links of london, barbour uk, supra shoes, replica watches, lancel, nike air max, moncler, moncler, moncler outlet, coach outlet, wedding dresses, canada goose outlet, pandora jewelry, karen millen uk, ugg, marc jacobs, juicy couture outlet, converse, moncler uk, louis vuitton, ugg pas cher, swarovski, pandora jewelry, gucci, canada goose, canada goose uk, ugg,uggs,uggs canada, pandora charms, juicy couture outlet, louis vuitton, louis vuitton, ray ban, ugg,ugg australia,ugg italia, canada goose jackets, swarovski crystal, canada goose, hollister, thomas sabo, canada goose outlet, toms shoes

At 2:27 AM, Blogger Unknown said...

louis vuitton outlet
kate spade outlet
nike trainers
coach factory outlet
air jordan retro
christian louboutin shoes
true religion outlet
michael kors handbags
adidas shoes
michael kors outlet
jordan 3
hollister kids
marc jacobs
ray ban outlet
louis vuitton handbags
mont blanc
adidas uk
michael kors handbags
nike nfl jerseys
caoch outlet
michael kors outlet
louis vuitton bags
timberland outlet
kobe bryant shoes
tory burch flats
adidas outlet store
coach outlet
christian louboutin sale
adidas originals shoes
lebron james shoes
coach factory outlet
tory burch outlet
burberry outlet online
polo ralph lauren
christian louboutin outlet
fitflop sandals
oakley vault
cartier watches

At 1:40 AM, Anonymous Cara Mengobati Radang Usus said...

This information is very useful. thank you for sharing. and I will also share information about health through the website

Cara Mengatasi sakit pundak dan Leher kaku
Cara Menghilangkan Benjolan di Bibir
Obat Nyeri haid
Tips Menghilangkan Wajah kusam
Cara Mengobati Bisul
solusi masalah kewanitaan


Post a Comment

<< Home