[Haskell-cafe] Wow you have to check this out Haskell
hello Haskell the holidays are coming up soon and I think this can help http://www.news13open.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Happy holidays Haskell
hello Haskell ever since I started this my life has been better than ever http://www.news13open.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Happy holidays Haskell
hey Haskell I didn't believe this at all until I started http://www.news13wise.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] hello Haskell
hey Haskell this is nuts http://www.business10i.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] hello Haskell
hey Haskell check it out http://www.fastnews10i.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] hi Haskell
hey Haskell i cant believe this http://www.fastnews10i.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] hello Haskell
hey Haskell this is sick http://www.bestsource10.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Span function
Can someone provide a hand calculation of: span ( 0) [-1, -2, -3, 0, 1, 2, -3, -4, -5]? I know the result is ([-1, -2, -3], [0, 1, 2, -3, -4, -5]), but the recursion flummoxes me. Here's the Prelude definition: mySpan :: (a - Bool) - [a] - ([a], [a])mySpan _ []= ([], [])mySpan p xs@(x:xs')| p x = (x:ys, zs)| otherwise= ([], xs) where (ys, zs) = mySpan p xs' Thanks. _ Hotmail has tools for the New Busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_1___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Removing alternate items from a list
What's the cleanest definition for a function f :: [a] - [a] that takes a list and returns the same list, with alternate items removed? e.g., f [0, 1, 2, 3, 4, 5] = [1,3,5]? _ The New Busy is not the old busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_3___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Declaring a tuple of instances of Enums as an instance of the Enum class
Say I've got a type Month declared as an instance of the Enum class, and a type MonthPair declared as a pair of months: data Month = January | February | March | April | May | June | July | August | September | October | November | December deriving (Eq, Enum, Ord, Show) type MonthPair = (Month, Month) deriving (Enum) The deriving on MonthPair gives me the error parse error on input 'deriving'. Why is this error generated? Is there a syntax error, or is there a conceptual problem with enumerating a Cartesian product, such as Month x Month? The cardinality of the Cartesian product is finite (including the bottom values, cardinality = 1 + (12 + 1)*(12 + 1) = 170), and so the product is amenable at least to some arbitrary enumeration (such as Cantor's diagonal method). Thanks. _ The New Busy think 9 to 5 is a cute idea. Combine multiple calendars with Hotmail. http://www.windowslive.com/campaign/thenewbusy?tile=multicalendarocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_5___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Clean proof?
Given the following definition of either, from the prelude:
either :: (a - c, b - c) - Either a b - c
either (f, g) (Left x) = f xeither (f, g) (Right x) = g x
what's a clean proof that:
h . either (f, g) = either (h . f, g . h)?
The only proof I can think of requires the introduction of an anonymous
function of z, with case analysis on z (Case 1: z = Left x, Case 2: z = Right
y), but the use of anonymous functions and case analysis is ugly, and I'm not
sure how to tie up the two cases neatly at the end. For example here's the
Left case:
h . either (f, g) ={definition of \} \z - (h . either (f,
g)) z ={definition of .} \z - (h (either (f, g) z)
={definition of either in case z = Left x} \z - (h (f x)) =
{definition of .} \z - (h . f) x ={definition of .} h . f
Thanks.
_
The New Busy is not the too busy. Combine all your e-mail accounts with Hotmail.
http://www.windowslive.com/campaign/thenewbusy?tile=multiaccountocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_4___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Clean proof -- correction
Correction: the theorem is
h . either (f, g) = either (h . f, h . g)
(Thanks to Lennart for pointing out the typo.)
From: rj248...@hotmail.com
To: haskell-cafe@haskell.org
Subject: Clean proof?
Date: Sun, 23 May 2010 15:41:20 +
Given the following definition of either, from the prelude:
either :: (a - c, b - c) - Either a b - c
either (f, g) (Left x) = f xeither (f, g) (Right x) = g x
what's a clean proof that:
h . either (f, g) = either (h . f, g . h)?
The only proof I can think of requires the introduction of an anonymous
function of z, with case analysis on z (Case 1: z = Left x, Case 2: z = Right
y), but the use of anonymous functions and case analysis is ugly, and I'm not
sure how to tie up the two cases neatly at the end. For example here's the
Left case:
h . either (f, g) ={definition of \} \z - (h . either (f,
g)) z ={definition of .} \z - (h (either (f, g) z)
={definition of either in case z = Left x} \z - (h (f x)) =
{definition of .} \z - (h . f) x ={definition of .} h . f
Thanks.
The New Busy is not the too busy. Combine all your e-mail accounts with
Hotmail. Get busy.
_
The New Busy is not the old busy. Search, chat and e-mail from your inbox.
http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_3___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] FW: Why does this Ord-class instance crash?
Why does the following, trivial code snippet below hang GHCi when I typeScalene Failure, and what's the fix? data Triangle = Failure | Equilateral | Isosceles | Scalene deriving (Eq, Show) instance Ord Triangle whereFailure Failure = FalseFailure _= True Equilateral Failure = FalseEquilateral Equilateral = False Equilateral _= True IsoscelesScalene = TrueIsosceles_= False Scalene _= False (I tried submitting this to beginn...@haskell.org, but even though I've signed up for that mailing list, I got a bounce-back saying that I needed admin approval to submit anything to that list, and I haven't heard from an admin, so I'm posting it here.) _ The New Busy is not the too busy. Combine all your e-mail accounts with Hotmail. http://www.windowslive.com/campaign/thenewbusy?tile=multiaccountocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_4___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Proof question -- (==) over Bool
I'm trying to prove that (==) is reflexive, symmetric, and transitive over the
Bools, given this definition:
(==) :: Bool - Bool - Boolx == y =
(x y) || (not x not y)
My question is: are the proofs below for reflexivity and symmetricity
rigorous, and what is the proof of transitivity, which eludes me? Thanks.
Theorem (reflexivity): For all x `elem` Bool, x == x.
Proof:
x == x ={definition of ==} (x x) || (not x not x) =
{logic (law of the excluded middle)} True
Theorem (symmetricity): For all x, y `elem` Bool, if x == y, then y == x.
Proof:
x == y ={definition of ==} (x y) || (not x not y) =
{lemma: () is commutative} (y x) || (not x not y) ={lemma:
() is commutative} (y x) || (not y not x) ={definition of
==} y == x
Theorem (transitivity): For all x, y, z `elem` Bool, if x == y, and y ==
z,then x == z.
Proof: ?
_
Hotmail has tools for the New Busy. Search, chat and e-mail from your inbox.
http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_1___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Enum instantiation
I'd like to make Day an instance of class Enum, but the definition of toEnum below seems to be completely wrong, because integers seem not permit pattern matching. How is toEnum defined? Thanks. data Day = Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday deriving (Eq, Ord, Show) instance Enum Day wherefromEnum Sunday= 0fromEnum Monday = 1fromEnum Tuesday = 2fromEnum Wednesday = 3fromEnum Thursday = 4fromEnum Friday= 5fromEnum Saturday = 6toEnum 0 = SundaytoEnum 1 = Monday toEnum 2 = TuesdaytoEnum 3 = Wednesday toEnum 4 = ThursdaytoEnum 5 = Friday toEnum 6 = Saturday _ Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_2___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Proof format
Is this how a rigorous Haskeller would lay out the proofs of the following
theorems? This is Bird 1.4.6.
(i)
Theorem: (*) x = (* x)
Proof:
(*) x ={definition of partial application} \y - x * y =
{commutativity of *} \y - y * x ={definition of (* x)} (* x)
(ii)
Theorem: (+) x = (x +)
Proof:
(+) x ={definition of partial application} \y - x + y =
{definition of (x +)} (x +)
(iii)
Theorem: (-) x /= (- x)
Proof:
(-) x ={definition of partial application} \y - x - y /=
{definition of prefix negation, which is not a section} (- x)
_
Hotmail is redefining busy with tools for the New Busy. Get more from your
inbox.
http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_2___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] (no subject)
This is another proof-layout question, this time from Bird 1.4.7. We're asked to define the functions curry2 and uncurry2 for currying and uncurrying functions with two arguments. Simple enough: curry2 :: ((a, b) - c) - (a - (b - c))curry2 f x y = f (x, y) uncurry2 :: (a - (b - c)) - ((a, b) - c)uncurry2 f (x, y) = f x y The following two assertions are obviously true theorems, but how are the formal proofs laid out? 1. curry2 (uncurry2 f) x y = f x y 2. uncurry2 (curry 2 f) (x, y) = f (x, y) _ The New Busy is not the too busy. Combine all your e-mail accounts with Hotmail. http://www.windowslive.com/campaign/thenewbusy?tile=multiaccountocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_4___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Bird problem 1.6.2 -- is there an easier method?
Bird problem 1.6.2 is: If f :: (a, b) - c, then define a function swap such that: flip (curry f) = curry (f . swap). I'd very much appreciate if someone could tell me whether there's a rigorous solution simpler than mine, which is: Since (.) :: (q - r) - (p - q) - (p - r), we have f :: q - r and swap :: p - q. Type unification of f requires q = (a, b) and r = c. Since f :: (a, b) - c and curry :: ((l, m) - n) - (l - m - n), typeunification requires l = a, b = m, and n = c. Therefore,curry :: ((a, b) - c) - (a - b - c), and (curry f) :: a - b - c. Since flip :: (s - t - u) - t - s - u, type unification requiress = a, t = b, and u = c. Therefore, flip :: (a - b - c) - b - a - c,and flip (curry f) :: b - a - c. Therefore, curry (f . swap) :: b - a - c, and p :: b - a. Therefore,swap :: b - a - (a, b), and: swap :: b - a - (a, b)swap x y = (y, x) _ Hotmail has tools for the New Busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_1___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Deducing a type signature
Bird 1.6.3 requires deducing type signatures for the functions strange and stranger. Are my solutions below correct? (i) strange f g = g (f g) Assume g :: a - b. Then f :: (a - b) - c. But since g :: a - b,f g :: a, so c = a. Therefore, f :: (a - b) - a, and g (f g) :: a.Therefore, strange :: ((a - b) - a) - (a - b) - a. (ii) stranger f = f f Assume f :: a - b. Since f f is well-typed, type unification requiresa = b. Therefore, f :: a - a, and stranger :: (a - a) - a. _ Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_2___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Help with Bird problem 1.4.1
Newbie trying to get through Bird. Could someone provide a clean solution, with proof (so I can see how these proofs are laid out), to this: Given: f :: Integer - Integerg :: Integer - (Integer - Integer) h :: ...h x y = f (g x y) Questions: a. Fill in the type assignment for h. b. Which of the following is true: (i) h = f . g (ii) h x = f . (g x) (iii) h x y = f . (g x y) _ Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_2___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Intuitive function given type signature
What are some simple functions that would naturally have the following type signatures: f :: (Integer - Integer) - Integer g :: (Integer - Integer) - (Integer - Integer) (Bird problem 1.4.5) _ Hotmail has tools for the New Busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_1___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Status of Haskell Platform for Snow Leopard
Could someone provide the status and expected release date of the Haskell Platform for Snow Leopard (Mac OS X 10.6.2)? Thanks. _ Your E-mail and More On-the-Go. Get Windows Live Hotmail Free. http://clk.atdmt.com/GBL/go/171222985/direct/01/___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How do I uninstall GHC on a Mac running Snow Leopard?
What's the cleanest way to fully uninstall GHC on a Mac running Snow Leopard? Running Library/Frameworks/GHC.framework/Tools/Uninstaller from an account with admin privileges produced the following, surprising error message: GHC.framework installer must be run with admin privileges Prefix command by 'sudo' logout [Process completed] Thanks as always. _ Windows 7: Simplify your PC. Learn more. http://www.microsoft.com/Windows/windows-7/default.aspx?ocid=PID24727::T:WLMTAGL:ON:WL:en-US:WWL_WIN_evergreen1:102009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Proof of duality theorem of fold?
I'm trying to prove the following duality theorem of fold for finite lists:
foldr f e xs = foldl (flip f) e (reverse xs)
where
reverse :: [a] - [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
flip :: (a - b - c) - b - a - c
flip f y x = f x y
foldr:: (a - b - b) - b - [a] - b
foldr f e [] = e
foldr f e (x : xs) = f x (foldr f e xs)
foldl:: (b - a - b) - b - [a] - b
foldl f e [] = e
foldl f e (x : xs) = foldl f (f e x) xs
I'm stuck on the induction case. Can someone help? Here's what I've got so
far:
Proof:
Case _|_.
Left-side reduction:
foldr f e _|_
= {case exhaustion of foldr}
_|_
Right-side reduction:
foldl (flip f) e (reverse _|_)
= {case exhaustion of reverse}
foldl (flip f) e _|_
= {case exhaustion of foldl}
_|_
Case [].
Left-side reduction:
foldr f e []
= {first equation of foldr}
e
Right-side reduction:
foldl (flip f) e (reverse [])
= {first equation of reverse}
foldl (flip f) e []
= {first equation of foldl}
e
Case (x : xs).
Left-side reduction:
foldr f e (x : xs)
= {second equation of foldr}
f x (foldr f e xs)
= {induction hypothesis: foldr f e xs = foldl (flip f) e (reverse xs)}
f x (foldl (flip f) e (reverse xs))
Right-side reduction:
foldl (flip f) e (reverse (x : xs))
= {second equation of reverse}
foldl (flip f) e (reverse xs ++ [x])
_
Hotmail® is up to 70% faster. Now good news travels really fast.
http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_HM_70faster_032009___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] A non-inductive Haskell proof?
The following theorem is obviously true, but how is it proved (most cleanly and simply) in Haskell? Theorem: (nondecreasing xs) = nondecreasing (insert x xs), where: nondecreasing :: (Ord a) = [a] - Bool nondecreasing []= True nondecreasing xxs@(x : xs) = and [a = b | (a, b) - zip xxs xs] insert :: (Ord a) = a - [a] - [a] insert x xs = takeWhile (= x) xs ++ [x] ++ dropWhile (= x) xs Thanks. _ Hotmail® is up to 70% faster. Now good news travels really fast. http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_HM_70faster_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Most elegant funciton for removing adjacent duplicates from a list using foldl and foldr
I need to write an implementation using foldl, and a separate implementation using foldr, of a function, remdups xs, that removes adjacent duplicate items from the list xs. For example, remdups [1,2,2,3,3,3,1,1]= [1,2,3,1]. My approach is first to write a direct recursion, as follows: remdups :: (Eq a) = [a] - [a] remdups []= [] remdups (x : []) = [x] remdups (x : xx : xs) = if x == xx then remdups (x : xs) else x : remdups (xx : xs) This code works, but it has three cases, not usual two, namely [] and (x : xs). What, if any, is the implementation using only two cases? Also, if three cases are required, then how can it be implemented using foldr, and how using foldl? Thanks. _ Express your personality in color! Preview and select themes for Hotmail®. http://www.windowslive-hotmail.com/LearnMore/personalize.aspx?ocid=TXT_MSGTX_WL_HM_express_032009#colortheme___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Help with Bird problem 4.5.6: sequence of successive maxima
This Bird problem vexes me, in the first instance because it doesn't seem to specify a unique solution: Given a list xs = [x_1, x_2, . . . , x_n], the sequence of successive maxima ssm xs is the longest subsequence [x_j1, x_j2, x_j3..x_jk] such that j_1 = 1 and j_m j_n = x_jm x_jn. For example, xs = [3, 1, 3, 4, 9, 2, 10, 7] = ssm xs = [3, 4, 9, 10]. Define ssm in terms of foldl. From this specification, I infer: ssm [] = [] ssm [1] = [1] ssm [1, 2, 3]= [1, 2, 3] ssm [1, 0, 3, 2] = [1, 3] However, what is ssm [1,0,100,2,3,4,5]? Is it [1, 100] or [1, 2, 3, 4, 5]? I think the latter, but am not certain. Whichever it is, what's the solution? Thanks. _ Windows Live™ Groups: Create an online spot for your favorite groups to meet. http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Proof of induction case of simple foldl identity.
Can someone provide the induction-case proof of the following identity:
foldl (-) ((-) x y) ys = (foldl (-) x ys) - y
If foldl is defined as usual:
foldl :: (b - a - b) - b - [a] - b
foldl f e [] = e
foldl f e (x : xs) = myFoldl f (f e x) xs
The first two cases, _|_ and [], are trivial.
Here's my best attempt at the (y : ys) case (the left and right sides reduce to
expressions that are obviously equal, but I don't know how to show it):
Case (y : ys).
Left-side reduction:
foldl (-) ((-) x y) (y : ys)
= {second equation of foldl}
foldl (-) ((-) ((-) x y) y) ys
= {notation}
foldl (-) ((-) (x - y) y) ys
= {notation}
foldl (-) ((x - y) - y) ys
= {arithmetic}
foldl (-) (x - 2 * y) ys
Right-side reduction:
(foldl (-) x (y : ys)) - y
= {second equation of foldl}
(foldl (-) ((-) x y) ys) - y
= {induction hypothesis: foldl (-) ((-) x y) ys = (foldl (-) x ys) - y}
((foldl (-) x ys) - y) - y
= {arithmetic}
(foldl (-) x ys) - 2 * y
Thanks as always.
_
Express your personality in color! Preview and select themes for Hotmail®.
http://www.windowslive-hotmail.com/LearnMore/personalize.aspx?ocid=TXT_MSGTX_WL_HM_express_032009#colortheme___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hand calculation of Bird's definition of zip using foldr
Can someone provide a complete hand calculation of zip [1,2,3] [4,5,6] using the following definition of zip, based on foldr: zip::[a] - [b] - [(a, b)] zip=foldr f e where e ys=[] f x g [ ]=[] f x g (y : ys)=(x , y) : g ys foldr::(a - b - b) - b - ([a] - b) foldr _ e []=e foldr f e (x : xs)=f x (foldr f e xs) This implementation of zip produces the expected result [(1, 4), (2, 5), (3, 6)], but I'm unable to do the hand calculation and don't understand why it works. Part of my problem is that e is defined as a function that takes one argument, I don't see how that fits in with the usual scheme for foldr, which, as I understand it, is: foldr f e [x1, x2, ...] = f x1 (f x2 (f x3 ...(f xn e)))... Thanks, as always, to all in this great community. _ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] A systematic method for deriving a defintion of foldl using foldr?
foldl and foldr are defined as follows: foldr:: (a - b - b) - b - [a] - b foldr f e [] = e foldr f e (x : xs) = f x (foldr f e xs) foldl:: (b - a - b) - b - [a] - b foldl f e [] = e foldl f e (x : xs) = foldl f (f e x) xs 1. I understand how these definitions work, and yet I'm unable to implement foldl in terms of foldr. What's a systematic approach to identifying such an implementation, and what is the implementation? 2. I believe that the reverse implementation--namely, implementing foldr in terms of foldl--is impossible. What's the proof of that? 3. Any advice on how, aside from tons of practice, to develop the intuition for rapidly seeing solutions to questions like these would be much appreciated. The difficulty a newbie faces in answering seemingly simple questions like these is quite discouraging. _ Express your personality in color! Preview and select themes for Hotmail®. http://www.windowslive-hotmail.com/LearnMore/personalize.aspx?ocid=TXT_MSGTX_WL_HM_express_032009#colortheme___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Horner's Rule, foldl, and direct recursion
Given a list of decimal digits represented by Integers between 0 and 9--for example, the list [1,2,3, 4]--with the high-order digit at the left, the list can be converted to a decimal integer n using the following formula, an instance of Horner's rule: n = 10 * 10 * 10 * 1 + 10 * 10 * 2 + 10 * 3 + 4 = 10 * (10 * 10 * 1 + 10 * 2 + 3) + 4 = 10 * (10 *(10 * 1 + 2) + 3) + 4 In Haskell, the foldl function neatly captures this pattern: horner :: [Integer] - Integer horner = myFoldl timesPlus 0 where timesPlus x y = 10 * x + y What is the direct recursive calculation of this function without using the call to foldl? In other words, what's the second equation of: horner2 :: [Integer] - Integer horner2 [] = 0 horner2 (x : xs) = ? Given that we've already got the definition using foldl, it ought to be easy to express the second equation, but it's eluding me. Thanks. _ Windows Live™ Groups: Create an online spot for your favorite groups to meet. http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Converting list comprehensions to combinatory style
Can anyone help with this problem from Bird: a. Convert the following list comprehensions to combinatory style: i. [(x, y) | x - [1..n], odd x, y - [1..n]] ii. [(x, y) | x - [1..n], y - [1..n], odd x] b. Are they equal? c. Compare the costs of evaluating the two expressions. I gather that by combinatory style, he means the use of concat, map, and filter. While Bird provides the following conversion rules, he doesn't prove them, justify them, or even provide an example using them: R1. [ f x | x - xs ] = map f xs R2. [ x | x - xs, p x ] = filter p xs R3. [ e | Q, P ] = concat [[e | P] | Q] R4. [ e | x - [d | P] ] = [e [x := d] | Q, P] Thanks. _ Windows Live™ Groups: Create an online spot for your favorite groups to meet. http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Naturality condition for inits
Here's another Bird problem that's stymied me: The function inits computes the list of initial segments of a list; its type is inits :: [a] - [[a]]. What is the appropriate naturality condition for inits? The only discussion in the text concerning naturality conditions concerns map, where the naturality conditions are stated in what seem to be quasi-commutativity laws over the composition operator, as follows: f . head= head . map f, where f is strict (i.e., f _|_ = _|_) map f . tail= tail . map f map f (xs ++ ys)= map f xs ++ map f ys map f . reverse = reverse . map f map f . concat = concat . map (map f) I believe that none of the following naturality conditions, extrapolated from those above, hold: a. head . inits = inits [head] b. tail . inits = inits . tail c. reverse . inits = inits . reverse d. concat . inits = inits . concat In case the definition of inits is relevant, my definition is: inits :: [a] - [[a]] inits xs = [take n xs | n - seglengths] where seglengths = [0..length xs] Thanks. _ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Type question re: map
Given the following (usual) definition of map: map:: (a - b) - [a] - [b] map f [] = [] map f (x : xs) = f x : map f xs What's the type of map map? GHCi's :t command reveals: *Main :t map map map map :: [a - b] - [[a] - [b]] I'd be grateful if anyone could provide a systematic type calculation so that I can reason through more complicated examples myself. Thanks. _ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Calculating with list comprehension
I can calculate non-nested list comprehensions without a problem, but am unable to calculate nested comprehensions involving, for example, the generation of a list of pairs where the first and separate elements are drawn from two separate lists, as in: [(a, b) | a - [1..3], b - [1..2]] How does one calculate the expansion of this list? The two rules for expanding list comprehensions are: 1. Generator rule: [e | x - xs, Q] = concat (map f xs) where f x = [e | Q] 2. Guard rule: [e | p, Q]= if p then [e | Q] else [] There is a third rule that I've seen on the Internet, not in an authoritative text: [e | Q1 , Q2] = concat [ [e | Q 2] | Q1 ] I don't understand what this third rule means, or whether it's relevant. Concat and map are defined as: concat :: [[a]] - [a] concat []= [] concat (xs:xss) = xs ++ concat xss map :: (a - b) - [a] - [b] map f [] = [] map f (x:xs) = f x : (map f xs) Any help is appreciated. _ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] (no subject)
Could someone provide an elegant solution to Bird problem 4.2.13? Here are the problem and my inelegant solution: Problem --- Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures concatenation as a primitive. For example, data (CatList a) = CatNil | Wrap a | Cat (CatList a) (CatList a) The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents x ++ y. However, since ++ is associative, the expressions Cat xs (Cat ys zs) and Cat (Cat xs ys) zs should be regarded as equal. Define appropriate instances of Eq and Ord for CatList. Inelegant Solution -- The following solution works: instance (Eq a) = Eq (CatList a) where CatNil == CatNil =True CatNil == Wrap z =False CatNil == Catz w = ( z == CatNil w == CatNil ) Wrap x== CatNil =False Wrap x== Wrap z =x == z Wrap x== Catz w = ( Wrap x == z w == CatNil ) || ( Wrap x == w z == CatNil ) Catx y == CatNil =x == CatNil y == CatNil Catx y == Wrap z = ( x == Wrap z y == CatNil ) || ( x == CatNil y == Wrap z ) Catx y == Catz w = unwrap (Cat x y) == unwrap (Cat z w) unwrap :: CatList a - [a] unwrap CatNil= [] unwrap (Wrap x) = [x] unwrap (Cat x y) = unwrap x ++ unwrap y instance (Eq a, Ord a) = Ord (CatList a) where x y = unwrap x unwrap y This solution correctly recognizes the equality of the following, including nested lists(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]): Wrap 1 == Cat (Wrap 1) CatNil Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) Wrap (Wrap 1)== Wrap (Cat (Wrap 1) CatNil) Although this solution works, it's a hack, because unwrap converts CatLists to lists. The question clearly seeks a pure solution that does not rely on Haskell's built-in lists. What's the pure solution that uses cases and recursion on CatList, not Haskell's built-in lists, to capture the equality of nested CatLists? _ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Interesting problem from Bird (4.2.13)
Could someone provide an elegant solution to Bird problem 4.2.13? Here are the problem and my inelegant solution: Problem --- Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures concatenation as a primitive. For example, data (CatList a) = CatNil | Wrap a | Cat (CatList a) (CatList a) The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents x ++ y. However, since ++ is associative, the expressions Cat xs (Cat ys zs) and Cat (Cat xs ys) zs should be regarded as equal. Define appropriate instances of Eq and Ord for CatList. Inelegant Solution -- The following solution works: instance (Eq a) = Eq (CatList a) where CatNil == CatNil =True CatNil == Wrap z =False CatNil == Catz w = ( z == CatNil w == CatNil ) Wrap x== CatNil =False Wrap x== Wrap z =x == z Wrap x== Catz w = ( Wrap x == z w == CatNil ) || ( Wrap x == w z == CatNil ) Catx y == CatNil =x == CatNil y == CatNil Catx y == Wrap z = ( x == Wrap z y == CatNil ) || ( x == CatNil y == Wrap z ) Catx y == Catz w = unwrap (Cat x y) == unwrap (Cat z w) unwrap :: CatList a - [a] unwrap CatNil= [] unwrap (Wrap x) = [x] unwrap (Cat x y) = unwrap x ++ unwrap y instance (Eq a, Ord a) = Ord (CatList a) where x y = unwrap x unwrap y This solution correctly recognizes the equality of the following, including nested lists(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]): Wrap 1 == Cat (Wrap 1) CatNil Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) Wrap (Wrap 1)== Wrap (Cat (Wrap 1) CatNil) Although this solution works, it's a hack, because unwrap converts CatLists to lists. The question clearly seeks a pure solution that does not rely on Haskell's built-in lists. What's the pure solution that uses cases and recursion on CatList, not Haskell's built-in lists, to capture the equality of nested CatLists? _ Windows Live™ Contacts: Organize your contact list. http://windowslive.com/connect/post/marcusatmicrosoft.spaces.live.com-Blog-cns!503D1D86EBB2B53C!2285.entry?ocid=TXT_TAGLM_WL_UGC_Contacts_032009___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
