[Haskell-beginners] Beginners Digest, Vol 40, Issue 27
Bob Walters-LT
bob at logictrust.com
Tue Oct 18 16:46:22 CEST 2011
please unsubscribe
On Oct 18, 2011, at 6:04 AM, beginners-request at haskell.org wrote:
> Send Beginners mailing list submissions to
> beginners at haskell.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://www.haskell.org/mailman/listinfo/beginners
> or, via email, send a message with subject or body 'help' to
> beginners-request at haskell.org
>
> You can reach the person managing the list at
> beginners-owner at haskell.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Beginners digest..."
>
>
> Today's Topics:
>
> 1. Re: newbie: Monad, equivalent notation using
> Control.Monad.guard (Brent Yorgey)
> 2. Re: recursion and pattern matching (Brent Yorgey)
> 3. Re: newbie: Monad, equivalent notation using
> Control.Monad.guard (Hugo Ferreira)
> 4. Weird (++) behavior when adding 2 vectors (Alexander Raasch)
> 5. Re: Weird (++) behavior when adding 2 vectors (Vlad Hanciuta)
> 6. Re: Weird (++) behavior when adding 2 vectors (Lorenzo Bolla)
> 7. Re: Weird (++) behavior when adding 2 vectors (Amy de Buitl?ir)
> 8. Re: Weird (++) behavior when adding 2 vectors (Alexander Raasch)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Tue, 18 Oct 2011 06:52:01 -0400
> From: Brent Yorgey <byorgey at seas.upenn.edu>
> Subject: Re: [Haskell-beginners] newbie: Monad, equivalent notation
> using Control.Monad.guard
> To: beginners at haskell.org
> Message-ID: <20111018105201.GA1102 at seas.upenn.edu>
> Content-Type: text/plain; charset=us-ascii
>
> On Tue, Oct 18, 2011 at 10:52:57AM +0100, Hugo Ferreira wrote:
>> Hello,
>>
>> On 10/17/2011 05:22 PM, Brent Yorgey wrote:
>>> On Mon, Oct 17, 2011 at 04:18:05PM +0100, Hugo Ferreira wrote:
>>>> Hello,
>>>>
>>>> I came across the following code:
>>>>
>>>> ngrams'' :: Int -> [a] -> [[a]]
>>>> ngrams'' n l = do
>>>> t<- Data.List.tails l
>>>> l<- [take n t]
>>>> Control.Monad.guard (length l == n)
>>>> return l
>>>>
>>>> and tried to use the ">>=" operator in order
>>>> to figure out how Monads work. I came up with:
>>>>
>>>> test l =
>>>> (Data.List.tails l)
>>>>>> = (\t -> [take 2 t])
>>>>>> = (\l -> if (length l == 2) then [l] else [])
>>>>
>>>> Questions:
>>>> 1. How can I use Control.Monad.guard directly in "test l"
>>>
>>> test l =
>>> (Data.List.tails l)
>>>>> = \t -> [take 2 t]
>>>>> = \l -> Control.Monad.guard (length l == 2)
>>>>> return l
>>>
>>> The rule is that
>>>
>>> x<- foo
>>>
>>> desugars to
>>>
>>> foo>>= \x -> ...
>>>
>>> and
>>>
>>> blah
>>>
>>> desugars to
>>>
>>> blah>> ...
>>>
>>
>> Ok, I was not aware of the >>.
>>
>>> One thing that might have been tripping you up is your extra
>>> parentheses around the lambda expressions. If you have
>>>
>>>>> = (\l -> ...)
>>>>> foo...
>>>
>>> the l does not scope over foo... so you cannot mention it. Instead
>>> what you want is
>>>
>>>>> = \l -> ...
>>>>> foo...
>>>
>>> so the lambda expression is actually \l -> ...>> foo..., that is,
>>> it includes *everything* after the \l -> ... and not just the stuff on
>>> that line.
>>>
>>
>> Hmmm. Still cannot wrap my mind around this B-(.
>>
>> [[1],[2],[3]] >>= \l -> func1 l >>= \m -> func2 m
>>
>> \l will hold each of the 3 elements of initial list
>> these are concatenated with the results of func1
>> results in a new list
>>
>> \m will have each element in the new list
>> these are concatenated with the results of func2
>> results in a last list
>>
>> is equal to ?
>>
>> (([[1],[2],[3]] >>= \l -> func1 l) >>= \m -> func2 m)
>
> Yes, your description is correct, and yes, these are equal. (Although
> the first is often more efficient.) They are required to be equal by
> the monad laws. However, consider
>
> [[1],[2],[3]] >>= \l -> func1 l >>= \m -> func2 m l
>
> and
>
> (([[1],[2],[3]] >>= \l -> func1 l) >>= \m -> func2 m l)
>
> Notice that func2 now takes a second argument. There is not even a
> question of whether these are equal: the second does not even compile,
> because the final 'l' is not in scope. This is the point I was trying
> to make.
>
> -Brent
>
>
>
> ------------------------------
>
> Message: 2
> Date: Tue, 18 Oct 2011 07:04:35 -0400
> From: Brent Yorgey <byorgey at seas.upenn.edu>
> Subject: Re: [Haskell-beginners] recursion and pattern matching
> To: beginners at haskell.org
> Message-ID: <20111018110435.GB1102 at seas.upenn.edu>
> Content-Type: text/plain; charset=iso-8859-1
>
> On Tue, Oct 18, 2011 at 01:34:14AM -0700, Alia wrote:
>> I have a question about what's the idiomatic way to walk a tree where there is also a requirement
>> for pattern-matching to draw variables out of the Node 'container':
>>
>>
>>
>> <Test.hs>
>>
>> module Test
>>
>> where
>>
>> data Tree a b = EmptyTree | Node a b [Tree a b]
>> ??????????? deriving (Show, Read, Eq)?
>> ?
>> t =? Node "goal" 1.0 [
>> ??????? Node "c1" 0.5 [
>> ??????????? Node "c3" 3.0 [
>> ??????????????? Node "c5" 1.0 []
>> ??????????????? ]
>> ??????????? ],
>> ??????? Node "c2" 0.5 [
>> ??????????? Node "c4" 2.0 []
>> ??????????? ]
>> ???? ]
>>
>>
>> sumTree :: (Num b) => Tree a b -> b
>> sumTree EmptyTree = 0
>> sumTree (Node _ value []) = value
>> sumTree (Node _ value [x]) = value + sumTree x
>> sumTree (Node name value (x:xs)) = value + sumTree x + sumTree (Node name 0 xs)
>>
>> depth :: Tree a b -> Int
>> depth EmptyTree = 0
>> depth (Node _ _ []) = 1
>> depth (Node _ _ [x]) = 1 + depth x
>> depth (Node n v (x:xs)) = 1 + depth (Node n v xs)?
>>
>> </Test.hs>
>>
>> Interactively:
>>
>> *Test> sumTree t
>> 8.0
>> *Test> depth t
>> 4
>> *Test>
>>
>>
>> This seems to work, but I have a sense that one should use folds and fmap and that there
>> is a better and cleaner what to do this.
>
> Your sense is absolutely right! =) You are not taking advantage of
> the fact that [] is a functor and can be folded over, etc. -- you have
> essentially hardcoded a list fold into your sumTree and depth
> functions. First let's rewrite sumTree. We use 'map' to call
> 'sumTree' recursively on all the child trees, then sum the results:
>
> sumTree :: (Num b) => Tree a b -> b
> sumTree EmptyTree = 0
> sumTree (Node _ value children) = value + sum (map sumTree children)
>
> Tada! We handled all those list cases (empty, single element, or
> cons) at once, in a general way.
>
> By the way, your implementation of 'depth' seems to be wrong: it only
> cares about the depth of the last child. I would think the idea would
> be to take the maximum depth of all the children and add one to that.
>
> I leave the rest for you:
>
> (1) rewrite depth in a similar way to sumTree, being sure to find
> the maximum depth of all the children
>
> (2) generalize both sumTree and depth to a treeFold function:
>
> treeFold :: c -> (a -> b -> [c] -> c) -> Tree a b -> c
>
> The first argument says what to do with EmptyTree, and the
> second argument says what to do with a Node.
>
> Once you have implemented treeFold you should be able to implement
> both sumTree and depth in terms of treeFold.
>
> Hope this helps. Let us know if you get stuck or have more questions!
>
> -Brent
>
>
>
> ------------------------------
>
> Message: 3
> Date: Tue, 18 Oct 2011 13:07:57 +0100
> From: Hugo Ferreira <hmf at inescporto.pt>
> Subject: Re: [Haskell-beginners] newbie: Monad, equivalent notation
> using Control.Monad.guard
> To: Brent Yorgey <byorgey at seas.upenn.edu>
> Cc: beginners at haskell.org
> Message-ID: <4E9D6C1D.7020409 at inescporto.pt>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> On 10/18/2011 11:52 AM, Brent Yorgey wrote:
>> On Tue, Oct 18, 2011 at 10:52:57AM +0100, Hugo Ferreira wrote:
>>> Hello,
>>>
>>> On 10/17/2011 05:22 PM, Brent Yorgey wrote:
>>>> On Mon, Oct 17, 2011 at 04:18:05PM +0100, Hugo Ferreira wrote:
>>>>> Hello,
>>>>>
>>>>> I came across the following code:
>>>>>
>>>>> ngrams'' :: Int -> [a] -> [[a]]
>>>>> ngrams'' n l = do
>>>>> t<- Data.List.tails l
>>>>> l<- [take n t]
>>>>> Control.Monad.guard (length l == n)
>>>>> return l
>>>>>
>>>>> and tried to use the ">>=" operator in order
>>>>> to figure out how Monads work. I came up with:
>>>>>
>>>>> test l =
>>>>> (Data.List.tails l)
>>>>>>> = (\t -> [take 2 t])
>>>>>>> = (\l -> if (length l == 2) then [l] else [])
>>>>>
>>>>> Questions:
>>>>> 1. How can I use Control.Monad.guard directly in "test l"
>>>>
>>>> test l =
>>>> (Data.List.tails l)
>>>>>> = \t -> [take 2 t]
>>>>>> = \l -> Control.Monad.guard (length l == 2)
>>>>>> return l
>>>>
>>>> The rule is that
>>>>
>>>> x<- foo
>>>>
>>>> desugars to
>>>>
>>>> foo>>= \x -> ...
>>>>
>>>> and
>>>>
>>>> blah
>>>>
>>>> desugars to
>>>>
>>>> blah>> ...
>>>>
>>>
>>> Ok, I was not aware of the>>.
>>>
>>>> One thing that might have been tripping you up is your extra
>>>> parentheses around the lambda expressions. If you have
>>>>
>>>>>> = (\l -> ...)
>>>>>> foo...
>>>>
>>>> the l does not scope over foo... so you cannot mention it. Instead
>>>> what you want is
>>>>
>>>>>> = \l -> ...
>>>>>> foo...
>>>>
>>>> so the lambda expression is actually \l -> ...>> foo..., that is,
>>>> it includes *everything* after the \l -> ... and not just the stuff on
>>>> that line.
>>>>
>>>
>>> Hmmm. Still cannot wrap my mind around this B-(.
>>>
>>> [[1],[2],[3]]>>= \l -> func1 l>>= \m -> func2 m
>>>
>>> \l will hold each of the 3 elements of initial list
>>> these are concatenated with the results of func1
>>> results in a new list
>>>
>>> \m will have each element in the new list
>>> these are concatenated with the results of func2
>>> results in a last list
>>>
>>> is equal to ?
>>>
>>> (([[1],[2],[3]]>>= \l -> func1 l)>>= \m -> func2 m)
>>
>> Yes, your description is correct, and yes, these are equal. (Although
>> the first is often more efficient.) They are required to be equal by
>> the monad laws. However, consider
>>
>> [[1],[2],[3]]>>= \l -> func1 l>>= \m -> func2 m l
>>
>> and
>>
>> (([[1],[2],[3]]>>= \l -> func1 l)>>= \m -> func2 m l)
>>
>> Notice that func2 now takes a second argument. There is not even a
>> question of whether these are equal: the second does not even compile,
>> because the final 'l' is not in scope. This is the point I was trying
>> to make.
>
> Aaaah. Got it.
>
> Thanks,
> Hugo F.
>
>>
>> -Brent
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>
>
>
>
> ------------------------------
>
> Message: 4
> Date: Tue, 18 Oct 2011 14:19:49 +0200
> From: Alexander Raasch <info at alexraasch.de>
> Subject: [Haskell-beginners] Weird (++) behavior when adding 2 vectors
> To: beginners at haskell.org
> Message-ID: <4E9D6EE5.6090207 at alexraasch.de>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Hi,
>
> so I wrote this function to add two vectors represented as lists:
>
> add a b = add' a b [] where
> add' [] [] s = s
> add' (a:as) (b:bs) s ++ [a+b]
>
> OK, I tried this in ghci:
>
>> add [1,2,3] [1,2,3]
> [6,4,2]
>
> Hm, I expected the result to be [2,4,6], of course, since the currently
> added components always go to the end of the resulting vector. I then
> changed the last term in add' to
>
> [a+b] ++ s ,
>
> but still
>
>> add [1,2,3] [1,2,3]
> [6,4,2]
>
> Can anyone explain this behavior to me. I think there should be some
> change in the result, no?
>
> Alex
>
>
>
> ------------------------------
>
> Message: 5
> Date: Tue, 18 Oct 2011 14:36:40 +0200
> From: Vlad Hanciuta <wladsh at gmail.com>
> Subject: Re: [Haskell-beginners] Weird (++) behavior when adding 2
> vectors
> To: Alexander Raasch <info at alexraasch.de>
> Cc: beginners at haskell.org
> Message-ID: <7C0687B5-7061-41E4-900C-FA0F1301B53C at gmail.com>
> Content-Type: text/plain; charset=us-ascii
>
> Hi,
>
> Your code is not valid syntactically, I guess the last equation for add' is "add' (a:as) (b:bs) s = add' as bs s ++ [a+b]". In that case, the function application binds stronger that ++ operator so the expression is actually equivalent to "(add' as bs s) ++ [a+b]". So you can easily see that the list is computed backwards.
>
> Vlad
>
> On 18 Oct 2011, at 14:19, Alexander Raasch wrote:
>
>> Hi,
>>
>> so I wrote this function to add two vectors represented as lists:
>>
>> add a b = add' a b [] where
>> add' [] [] s = s
>> add' (a:as) (b:bs) s ++ [a+b]
>>
>> OK, I tried this in ghci:
>>
>>> add [1,2,3] [1,2,3]
>> [6,4,2]
>>
>> Hm, I expected the result to be [2,4,6], of course, since the currently added components always go to the end of the resulting vector. I then changed the last term in add' to
>>
>> [a+b] ++ s ,
>>
>> but still
>>
>>> add [1,2,3] [1,2,3]
>> [6,4,2]
>>
>> Can anyone explain this behavior to me. I think there should be some change in the result, no?
>>
>> Alex
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
>
> ------------------------------
>
> Message: 6
> Date: Tue, 18 Oct 2011 13:48:40 +0100
> From: Lorenzo Bolla <lbolla at gmail.com>
> Subject: Re: [Haskell-beginners] Weird (++) behavior when adding 2
> vectors
> To: Alexander Raasch <info at alexraasch.de>
> Cc: beginners at haskell.org
> Message-ID:
> <CADjgTRzTafiyMwFuNd8UYyMw7Djxvf-7SNespN8W5hKSm7mhUA at mail.gmail.com>
> Content-Type: text/plain; charset="utf-8"
>
> Hi,
>
> On Tue, Oct 18, 2011 at 1:19 PM, Alexander Raasch <info at alexraasch.de>wrote:
>
>> Hi,
>>
>> so I wrote this function to add two vectors represented as lists:
>>
>> add a b = add' a b [] where
>> add' [] [] s = s
>> add' (a:as) (b:bs) s ++ [a+b]
>>
>>
> I think something mangled your function, as this is not valid Haskell code.
>
> Anyway, I tried to rewrite your function.
> The first version works as expected; the second gives reversed output.
> Note that there is no need for the accumulator "s".
>
> add a b = add' a b
> where add' [] [] = []
> add' (a:as) (b:bs) = [a+b] ++ (add' as bs)
>
> add a b = add' a b
> where add' [] [] = []
> add' (a:as) (b:bs) = (add' as bs) ++ [a+b] -- reversed output
>
> Obviously, the same function can be written as:
> zipWith (+) [1,2,3] [1,2,3]
>
> hth,
> L.
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <http://www.haskell.org/pipermail/beginners/attachments/20111018/159bbe5b/attachment-0001.htm>
>
> ------------------------------
>
> Message: 7
> Date: Tue, 18 Oct 2011 12:51:27 +0000 (UTC)
> From: Amy de Buitl?ir <amy at nualeargais.ie>
> Subject: Re: [Haskell-beginners] Weird (++) behavior when adding 2
> vectors
> To: beginners at haskell.org
> Message-ID: <loom.20111018T144110-785 at post.gmane.org>
> Content-Type: text/plain; charset=us-ascii
>
> There seems to be something missing from this line:
>> add' (a:as) (b:bs) s ++ [a+b]
>
> Assuming you want to write your own function as an exercise, you could write it
> as a recursive function like this:
>
> add [] b = b
> add a [] = a
> add (a:as) (b:bs) = (a+b) : (add as bs)
>
> FYI, the easiest way to accomplish what you want is:
>
> add = zipWith (+)
>
> which is equivalent to:
>
> add a b = zipWith (+) a b
>
>
> Hope that helps
>
>
>
>
> ------------------------------
>
> Message: 8
> Date: Tue, 18 Oct 2011 15:04:25 +0200
> From: Alexander Raasch <info at alexraasch.de>
> Subject: Re: [Haskell-beginners] Weird (++) behavior when adding 2
> vectors
> To: beginners at haskell.org
> Message-ID: <4E9D7959.7090807 at alexraasch.de>
> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>
> Hi,
>
> thanks for your answers. I'm exercising with different programming
> techniques, so the use of an accumulator was intentional although not
> necessary. As Vlad said, my mistake was the stronger binding of the
> function application. Sigh, ...
>
> Thank you all again.
>
> Alex
>
> On 10/18/2011 02:48 PM, Lorenzo Bolla wrote:
>> Hi,
>>
>> On Tue, Oct 18, 2011 at 1:19 PM, Alexander Raasch <info at alexraasch.de
>> <mailto:info at alexraasch.de>> wrote:
>>
>> Hi,
>>
>> so I wrote this function to add two vectors represented as lists:
>>
>> add a b = add' a b [] where
>> add' [] [] s = s
>> add' (a:as) (b:bs) s ++ [a+b]
>>
>>
>> I think something mangled your function, as this is not valid Haskell
>> code.
>>
>> Anyway, I tried to rewrite your function.
>> The first version works as expected; the second gives reversed output.
>> Note that there is no need for the accumulator "s".
>>
>> add a b = add' a b
>> where add' [] [] = []
>> add' (a:as) (b:bs) = [a+b] ++ (add' as bs)
>>
>> add a b = add' a b
>> where add' [] [] = []
>> add' (a:as) (b:bs) = (add' as bs) ++ [a+b] -- reversed
>> output
>>
>> Obviously, the same function can be written as:
>> zipWith (+) [1,2,3] [1,2,3]
>>
>> hth,
>> L.
>
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <http://www.haskell.org/pipermail/beginners/attachments/20111018/a500e224/attachment.htm>
>
> ------------------------------
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
> End of Beginners Digest, Vol 40, Issue 27
> *****************************************
More information about the Beginners
mailing list