Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Adapting code from an imperative loop (Bob Ippolito)
2. Re: 'Simple' function (Imants Cekusins)
3. Re: Adapting code from an imperative loop (Michael Orlitzky)
4. Re: Adapting code from an imperative loop (Chadda? Fouch?)
----------------------------------------------------------------------
Message: 1
Date: Fri, 19 Jun 2015 14:18:33 +0200
From: Bob Ippolito <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Adapting code from an imperative loop
Message-ID:
<CACwMPm-ymB+5tFNoWtHhjOSUYN9+OWyn4_=0mzp47a28wc7...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
An example of a function of (a -> a -> a) would be (+), which works if your
values are numbers (which mirrors your Python-like pseudocode).
On Friday, June 19, 2015, Matt Williams <[email protected]>
wrote:
> Dear All,
>
> Thanks for your help with this.
>
> I have got the simple version working but now need to use
> Map.fromListWith, and am having syntax problems.
>
> I found a related question on Stack overflow (here: http://
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> stackoverflow.com
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> /questions/15514486/
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> haskell-converting-a-list-
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> of-
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> a-b-key-
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> value-pairs-
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> with-
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> possibly-
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> repeated-key
> <http://stackoverflow.com/questions/15514486/haskell-converting-a-list-of-a-b-key-value-pairs-with-possibly-repeated-key>
> ).
>
> However, I'm having problems understanding the additional function. The
> signature should be :
> (a -> a -> a) -> [(k, a)] -> Map
>
> And so I assume I need to supply a function whose signature is:
>
> (a -> a -> a)
>
> Is that correct?
>
> Thanks,
> Matt
>
> On Fri, 19 Jun 2015 09:04 Vlatko Basic <[email protected]
> <javascript:_e(%7B%7D,'cvml','[email protected]');>> wrote:
>
>> To learn, I'd suggest you implement it first with the recursion (a tip:
>> use a "loop" function in where clause), and than with fold. Those are
>> important features to understand in Haskell. Try to use the "higher-level"
>> functions as little as possible until you grasp the basics (like fold
>> syntax).
>>
>> If you just need any solution, fromListWith is fine.
>>
>> br,
>> vlatko
>>
>>
>>
>> -------- Original Message --------
>> Subject: Re: [Haskell-beginners] Adapting code from an imperative loop
>> From: Matt Williams <[email protected]>
>> <javascript:_e(%7B%7D,'cvml','[email protected]');>
>> To: The Haskell-Beginners Mailing List - Discussion of primarily
>> beginner-level topics related to Haskell <[email protected]>
>> <javascript:_e(%7B%7D,'cvml','[email protected]');>
>> Date: 19/06/15 09:05
>>
>>
>> I tried doing it as a fold (the pattern of accumulating a value, where
>> the accumulated value was the resulting Map), but couldn't manage the
>> syntax.
>>
>> Have now got it partially working with fromListWith.
>>
>> Thanks a lot,
>> Matt
>>
>> On Fri, 19 Jun 2015 07:18 Bob Ippolito <
>> <javascript:_e(%7B%7D,'cvml','[email protected]');>[email protected]
>> <javascript:_e(%7B%7D,'cvml','[email protected]');>> wrote:
>>
>>> On Friday, June 19, 2015, Matt Williams <[email protected]
>>> <javascript:_e(%7B%7D,'cvml','[email protected]');>> wrote:
>>>
>>>> Dear All,
>>>>
>>>> I have been wrestling with this for a while now.
>>>>
>>>> I have a list of data items, and want to be able to access them, in a
>>>> Hash Map, via a short summary of their characteristics.
>>>>
>>>> In an imperative language this might look like:
>>>>
>>>> myMap = new map()
>>>> for elem in myElems:
>>>> key = makeKey(elem)
>>>> myMap[key] = myMap[key] + elem
>>>>
>>>> I have been trying to do this in Haskell, but am stuck on how to hand
>>>> the Map back to itself each time.
>>>>
>>>> I have a function :: elem -> [p,q] to make the key, but the Map.insert
>>>> function has the following signature:
>>>>
>>>> insert :: (Hashable
>>>> <https://hackage.haskell.org/package/hashmap-1.0.0.2/docs/Data-Hashable.html#t:Hashable>
>>>> k, Ord
>>>> <https://hackage.haskell.org/packages/archive/base/4.2.0.2/doc/html/Data-Ord.html#t:Ord>
>>>> k)
>>>> => k -> a -> HashMap
>>>> <https://hackage.haskell.org/package/hashmap-1.0.0.2/docs/Data-HashMap.html#t:HashMap>
>>>> k
>>>> a -> HashMap
>>>> <https://hackage.haskell.org/package/hashmap-1.0.0.2/docs/Data-HashMap.html#t:HashMap>
>>>> k
>>>> a
>>>>
>>>> My thought was that I needed to go through the list of the elems, and
>>>> at each point add them to the Hash Map, handing the updated Map onto the
>>>> next step - but this is what I cannot write.
>>>>
>>>
>>> This is typically done with fromListWith or a combination of foldl'
>>> and insertWith or alter.
>>>
>>> -bob
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> <javascript:_e(%7B%7D,'cvml','[email protected]');>
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>
>>
>> _______________________________________________
>> Beginners mailing [email protected]
>> <javascript:_e(%7B%7D,'cvml','[email protected]');>http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> <javascript:_e(%7B%7D,'cvml','[email protected]');>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150619/13af2262/attachment-0001.html>
------------------------------
Message: 2
Date: Fri, 19 Jun 2015 14:43:47 +0200
From: Imants Cekusins <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] 'Simple' function
Message-ID:
<CAP1qinay=An-+7buUJPTZgZjw7z011Pxg1fgy=6u3nkhuo3...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
impossible:
asString :: IO String -> String
here is an article which in addition to this thread clarified it for me:
https://wiki.haskell.org/All_About_Monads
search for:
4.3 No way out
The IO monad is a familiar example of a one-way monad in Haskell.
Because you can't escape from the IO monad, it is impossible to write
a function that does a computation in the IO monad but whose result
type does not include the IO type constructor. This means that any
function whose result type does not contain the IO type constructor is
guaranteed not to use the IO monad.
...
There is no way to get rid of the IO type constructor in the signature
of any function that uses it, so the IO type constructor acts as a
kind of tag that identifies all functions that do I/O. Furthermore,
such functions are only useful within the IO monad. So a one-way monad
effectively creates an isolated computational domain in which the
rules of a pure functional language can be relaxed. Functional
computations can move into the domain, but dangerous side-effects and
non-referentially-transparent functions cannot escape from it.
------------------------------
Message: 3
Date: Fri, 19 Jun 2015 13:05:20 -0400
From: Michael Orlitzky <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Adapting code from an imperative loop
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
On 06/19/2015 01:51 AM, Matt Williams wrote:
>
> In an imperative language this might look like:
>
> myMap = new map()
> for elem in myElems:
> key = makeKey(elem)
> myMap[key] = myMap[key] + elem
>
> ...
>
> My thought was that I needed to go through the list of the elems, and at
> each point add them to the Hash Map, handing the updated Map onto the
> next step - but this is what I cannot write.
>
Your thought was right. You want to go through the list of elems,
building up a new value (the hash map) as you go. The pattern is called
a fold, as others have mentioned. The only tricky part is gluing
together the pieces.
Your pseudocode above looks like it assumes that myMap[key] will return
zero if `key` isn't present in `myMap`. I think I've managed to
reproduce what you want. The "key from element" function I used is just
the identity function, but you should be able to adapt it.
module Main
where
import Data.Map (Map, empty, insert)
import qualified Data.Map as M (lookup)
key_from_elem :: Int -> Int
key_from_elem = id
loop :: [Int] -> (Map Int Int) -> (Map Int Int)
loop elems initial_map =
foldr update_map initial_map elems
where
update_map :: Int -> (Map Int Int) -> (Map Int Int)
update_map x m =
let k = key_from_elem x in
case (M.lookup k m) of
Nothing -> insert k x m
Just v -> insert k (v + x) m
main :: IO ()
main = do
let elems = [1,2,3,4,5]
let l1 = loop elems empty
print l1
let l2 = loop elems l1
print l2
let l3 = loop elems l2
print l3
------------------------------
Message: 4
Date: Fri, 19 Jun 2015 18:49:29 +0000
From: Chadda? Fouch? <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Adapting code from an imperative loop
Message-ID:
<canfjzrzlkr+yjes+ga74k35z0j9sksfhzatppttj-av-d3k...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Le ven. 19 juin 2015 ? 19:03, Michael Orlitzky <[email protected]> a
?crit :
> loop :: [Int] -> (Map Int Int) -> (Map Int Int)
> loop elems initial_map =
> foldr update_map initial_map elems
> where
> update_map :: Int -> (Map Int Int) -> (Map Int Int)
> update_map x m =
> let k = key_from_elem x in
> case (M.lookup k m) of
> Nothing -> insert k x m
> Just v -> insert k (v + x) m
>
While this code will do the right thing, it won't do it efficiently, at
all !
First (and huge) problem is using foldr : starting from the end of the list
is the wrong move here if you want to consume your Int stream efficiently
(which you probably do and which is vital if the stream is big). So you
should be using foldl' and the strict version of Map (Data.Map.Strict).
Also, though less important, looking up a key then updating the value with
insert is wasteful : you will be doing the search twice, instead of using
one of the nice combinators of Data.Map which find and update a value in
one pass like "insertWith (+) k x m"
In other words :
import qualified Data.Map.Strict as M
countingMap :: [(key, Int)] -> Map key Int
countingMap kvs = foldl' update M.empty kvs
where update (k,v) m = M.insertWith (+) k v m
Since this is a very common need, there's even a combinator to do this :
countingMap :: [(key, Int)] -> Map key Int
countingMap kvs = M.fromListWith (+) kvs
At which point you may even use directly this code and forgo creating a
function for it (except if you're using it several times or as a minor step
in a big pipeline where you would like to label each step clearly).
--
Jeda?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150619/876fcafd/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 84, Issue 32
*****************************************
