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. Dependent and independent variables in foldl and foldr
(Lawrence Bottorff)
2. Re: Dependent and independent variables in foldl and foldr
(Francesco Ariis)
3. list, map, sequence - stack overflow and performance issues
(Julian Ong)
4. Re: list, map, sequence - stack overflow and performance
issues (Julian Ong)
----------------------------------------------------------------------
Message: 1
Date: Sat, 16 Jan 2021 16:10:47 -0600
From: Lawrence Bottorff <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Dependent and independent variables in
foldl and foldr
Message-ID:
<cafahfsupakzvypecx2sk+neeawawuomnfabnqrd9jggsbwy...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I have this
myLength1 = foldl (\n _ -> n + 1) 0
and this
myLength2 = foldr (\_ n -> n + 1) 0
I am guessing that foldl knows to assign the accumulator-seed argument to
the dependent variable and the list argument's elements recursively to the
independent variable; and with foldr to do the opposite. Is this a fair
assumption? BTW, where can I get a look at the code for fold functions; or
does the type definition answer my original question? Not really able to
decipher it so well
:t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
LB
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20210116/64eb4f96/attachment-0001.html>
------------------------------
Message: 2
Date: Sat, 16 Jan 2021 23:35:55 +0100
From: Francesco Ariis <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Dependent and independent variables
in foldl and foldr
Message-ID: <20210116223555.GA25810@extensa>
Content-Type: text/plain; charset=utf-8
Il 16 gennaio 2021 alle 16:10 Lawrence Bottorff ha scritto:
> I have this
>
> myLength1 = foldl (\n _ -> n + 1) 0
>
> and this
>
> myLength2 = foldr (\_ n -> n + 1) 0
>
> I am guessing that foldl knows to assign the accumulator-seed argument to
> the dependent variable and the list argument's elements recursively to the
> independent variable; and with foldr to do the opposite. Is this a fair
> assumption? BTW, where can I get a look at the code for fold functions; or
> does the type definition answer my original question? Not really able to
> decipher it so well
>
> :t foldl
> foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl and foldr have slightly different signatures,
λ> :t +d foldl
foldl :: (b -> a -> b) -> b -> [a] -> b
λ> :t +d foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
(Notice `b -> a -> b` vs. `a -> b -> b`), hence the lambdas have a
different non-matched parameter.
Does this answer your question? —F
------------------------------
Message: 3
Date: Sun, 17 Jan 2021 00:14:47 +0000 (UTC)
From: Julian Ong <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of Primarily
Beginner-level Topics Related To Haskell <[email protected]>
Subject: [Haskell-beginners] list, map, sequence - stack overflow and
performance issues
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
Hi Haskellers - I'm learning Haskell and attempting to solve the Advent of Code
2020 puzzles using Haskell. I'm stuck on part 2 of Day 15 and have been for a
while now, so I'm reaching out.
The puzzle asks you to find the nth element in a list of integers. Here's how
the list is constructed:
Start with a seed list of integers, like [0,3,6]. Then, referring to the last
element (6), the next element is given by these rules:
- If the last element was the first time the element has appeared in the
list, then the next element is 0.
- Otherwise, the next element is the age, or distance in the number of index
positions, between the last element and when it last appeared before that.
For example, starting with [0,3,6], the next elements are 0, 3, 3, 1, 0, 4, 0,
etc.
Part 1 of the puzzle asks you to find the 2020th element in the list.
You can do this by constructing increasingly longer lists like this (using
Data.List):
nextNum :: [Int] -> [Int]nextNum l@(x:xs) = if not (x `elem` xs) then 0 : l
else age l : l where age (x:xs) = let Just i = elemIndex x xs
in i+1
Then:
head $ (iterate nextNum [6,3,0]) !! 2017
will give you the 2020th element of 436.
Note that you provide the starting list in reverse order and iterate so that it
will keep adding new elements to the head of the list, which is more efficient
than adding to the end.
You can also use unfoldr to generate the list element by element like this:
nextNum' :: [Int] -> IntnextNum' (x:xs) = if not (x `elem` xs) then 0 else age
x xs where age x xs = let Just i = elemIndex x xs
in i+1
Then:
(unfoldr (\l -> Just (nextNum' l, nextNum' l : l)) slist) !! 2016
will give you the 2020th element of 436.
---
Part 2 of the puzzle asks you to find the 30000000th element given starting
list [9,3,1,0,8,4].
I cannot find a way to do this without stack overflow and performance issues
(I've run my attempts overnight with no answer generated). I've tried using
Data.Map and Data.Sequence because my Stack Overflow searching suggested these
might be more efficient data structures for this sort of task. Here are my
attempts:
-- Uses Data.Map to avoid duplicate numbers thereby shortening the list. The
dictionary entry (k, v) gives the element and the last position of that element.
nextNum'' :: (IntMap Int, (Int, Int)) -> (IntMap Int, (Int, Int))nextNum''
(mp, (k, v)) = case IntMap.lookup k mp of Nothing -> (IntMap.insert k v mp,
(0, v+1)) Just pos -> (IntMap.insert k v mp, (v-pos, v+1))
Then:
snd $ (iterate nextNum'' (IntMap.fromList [(0,1),(3,2)],(6,3))) !! 2017
provides the answer for the 2020th element but either stack overflows or runs
for hours (if I use a strict version of iterate) trying to figure out the
30000000th element.
Similarly, using Data.Sequence, I tried:
nextNum''' :: Seq Int -> IntnextNum'''' (xs :|> x) = if not (x `elem` xs) then
0 else age x xs where age x xs = let Just i = Seq.elemIndexR x xs
in Seq.length xs - i
aoc15b' :: Seq Int -> Int -> Intaoc15b' slist tnum = (\(xs :> x) -> x) $
Seq.viewr (Seq.unfoldr (\l -> if Seq.length l == tnum then Nothing else let
nnum = force (nextNum'''' l) in Just (nnum, force (l |> nnum))) slist)
I found that I needed to fix stack overflow problems by using "force" from
Control.DeepSeq. Despite seemingly fixing stack overflow issues though, the
calculation just takes too long, and in fact, I have never been able to
actually output a solution.
I thought that using Data.Map or Data.Sequence would speed things up based on
my Stack Overflow searching, but I'm unable to come up with a Haskell solution
that runs in reasonable time.
I'm at a loss for different strategies at this point and would appreciate any
ideas from the community.
Thanks, Julian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20210117/3275328d/attachment-0001.html>
------------------------------
Message: 4
Date: Sun, 17 Jan 2021 00:20:29 +0000 (UTC)
From: Julian Ong <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of Primarily
Beginner-level Topics Related To Haskell <[email protected]>
Subject: Re: [Haskell-beginners] list, map, sequence - stack overflow
and performance issues
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
Sorry, corrected some typos below in the number of apostrophes.
On Saturday, January 16, 2021, 04:14:47 PM PST, Julian Ong
<[email protected]> wrote:
Hi Haskellers - I'm learning Haskell and attempting to solve the Advent of
Code 2020 puzzles using Haskell. I'm stuck on part 2 of Day 15 and have been
for a while now, so I'm reaching out.
The puzzle asks you to find the nth element in a list of integers. Here's how
the list is constructed:
Start with a seed list of integers, like [0,3,6]. Then, referring to the last
element (6), the next element is given by these rules:
- If the last element was the first time the element has appeared in the
list, then the next element is 0.
- Otherwise, the next element is the age, or distance in the number of index
positions, between the last element and when it last appeared before that.
For example, starting with [0,3,6], the next elements are 0, 3, 3, 1, 0, 4, 0,
etc.
Part 1 of the puzzle asks you to find the 2020th element in the list.
You can do this by constructing increasingly longer lists like this (using
Data.List):
nextNum :: [Int] -> [Int]nextNum l@(x:xs) = if not (x `elem` xs) then 0 : l
else age l : l where age (x:xs) = let Just i = elemIndex x xs
in i+1
Then:
head $ (iterate nextNum [6,3,0]) !! 2017
will give you the 2020th element of 436.
Note that you provide the starting list in reverse order and iterate so that it
will keep adding new elements to the head of the list, which is more efficient
than adding to the end.
You can also use unfoldr to generate the list element by element like this:
nextNum' :: [Int] -> IntnextNum' (x:xs) = if not (x `elem` xs) then 0 else age
x xs where age x xs = let Just i = elemIndex x xs
in i+1
Then:
(unfoldr (\l -> Just (nextNum' l, nextNum' l : l)) slist) !! 2016
will give you the 2020th element of 436.
---
Part 2 of the puzzle asks you to find the 30000000th element given starting
list [9,3,1,0,8,4].
I cannot find a way to do this without stack overflow and performance issues
(I've run my attempts overnight with no answer generated). I've tried using
Data.Map and Data.Sequence because my Stack Overflow searching suggested these
might be more efficient data structures for this sort of task. Here are my
attempts:
-- Uses Data.Map to avoid duplicate numbers thereby shortening the list. The
dictionary entry (k, v) gives the element and the last position of that element.
nextNum'' :: (IntMap Int, (Int, Int)) -> (IntMap Int, (Int, Int))nextNum''
(mp, (k, v)) = case IntMap.lookup k mp of Nothing -> (IntMap.insert k v mp,
(0, v+1)) Just pos -> (IntMap.insert k v mp, (v-pos, v+1))
Then:
snd $ (iterate nextNum'' (IntMap.fromList [(0,1),(3,2)],(6,3))) !! 2017
provides the answer for the 2020th element but either stack overflows or runs
for hours (if I use a strict version of iterate) trying to figure out the
30000000th element.
Similarly, using Data.Sequence, I tried:
nextNum''' :: Seq Int -> IntnextNum''' (xs :|> x) = if not (x `elem` xs) then
0 else age x xs where age x xs = let Just i = Seq.elemIndexR x xs
in Seq.length xs - i
aoc15b' :: Seq Int -> Int -> Intaoc15b' slist tnum = (\(xs :> x) -> x) $
Seq.viewr (Seq.unfoldr (\l -> if Seq.length l == tnum then Nothing else let
nnum = force (nextNum''' l) in Just (nnum, force (l |> nnum))) slist)
I found that I needed to fix stack overflow problems by using "force" from
Control.DeepSeq. Despite seemingly fixing stack overflow issues though, the
calculation just takes too long, and in fact, I have never been able to
actually output a solution.
I thought that using Data.Map or Data.Sequence would speed things up based on
my Stack Overflow searching, but I'm unable to come up with a Haskell solution
that runs in reasonable time.
I'm at a loss for different strategies at this point and would appreciate any
ideas from the community.
Thanks, Julian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20210117/014d4a90/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 150, Issue 7
*****************************************
