Adapting code from an imperative loop

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Adapting code from an imperative loop

Matt Williams-2

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 k, Ord k) => k -> a -> HashMap k a -> 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.

Any help much appreciated.

Thanks,
Matt

   
   


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Adapting code from an imperative loop

Bob Ippolito
On Friday, June 19, 2015, Matt Williams <[hidden email]> 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 k, Ord k) => k -> a -> HashMap k a -> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Adapting code from an imperative loop

Matt Williams-2

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 <[hidden email]> wrote:
On Friday, June 19, 2015, Matt Williams <[hidden email]> 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 k, Ord k) => k -> a -> HashMap k a -> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Adapting code from an imperative loop

Vlatko Basic
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 [hidden email]
To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell [hidden email]
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 <[hidden email]> wrote:
On Friday, June 19, 2015, Matt Williams <[hidden email]> 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 k, Ord k) => k -> a -> HashMap k a -> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Adapting code from an imperative loop

Matt Williams-2

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://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 <[hidden email]> 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 [hidden email]
To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell [hidden email]
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 <[hidden email]> wrote:
On Friday, June 19, 2015, Matt Williams <[hidden email]> 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 k, Ord k) => k -> a -> HashMap k a -> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Adapting code from an imperative loop

Bob Ippolito
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 <[hidden email]> 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://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 <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;vlatko.basic@gmail.com&#39;);" target="_blank">vlatko.basic@...> 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 <a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;matt.williams45.mw@gmail.com&#39;);" target="_blank"><matt.williams45.mw@...>
To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;beginners@haskell.org&#39;);" target="_blank"><beginners@...>
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 <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;bob@redivi.com&#39;);" target="_blank"><a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;bob@redivi.com&#39;);" target="_blank">bob@...> wrote:
On Friday, June 19, 2015, Matt Williams <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;matt.williams45.mw@gmail.com&#39;);" target="_blank">matt.williams45.mw@...> 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 k, Ord k) => k -> a -> HashMap k a -> 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
<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;Beginners@haskell.org&#39;);" target="_blank">Beginners@...
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;Beginners@haskell.org&#39;);" target="_blank">Beginners@...
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;Beginners@haskell.org&#39;);" target="_blank">Beginners@...
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Adapting code from an imperative loop

Michael Orlitzky
In reply to this post by Matt Williams-2
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

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Adapting code from an imperative loop

Chaddaï Fouché
Le ven. 19 juin 2015 à 19:03, Michael Orlitzky <[hidden email]> 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ï

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners