70192

haskell running out of memory with finite lists

<h3>Question</h3>

I run out of memory trying to run moderate inputs such as this:

variation_models 15 25

also running higher numbers for ncars seems to make a huge difference in speed and memory usage.

The slowdown is expected (there are more things to compare), but the exponential increase of memory usage doesn't make sense to me

<pre class="lang-hs prettyprint-override">import Control.Monad orderedq f [] = True orderedq f (x:[]) = True orderedq f (x:y:zs) = f x y && orderedq f (y:zs) num_orderedq = orderedq (<=) adds_up_to n xs = n == sum xs both_conditions f g xs = f xs && g xs variation_models ncars nlocations = filter (both_conditions (adds_up_to nlocations) num_orderedq) $ replicateM ncars [1..nlocations-ncars+1]

What is causing the large difference in memory usage? replicateM?


<h3>Answer1:</h3>

I think you've seen elsewhere that your specific problem (creating ordered lists of integers that sum to a given number) is better solved using an alternative algorithm, rather than filtering a huge list of lists of integers.

However, getting back to your original issue, it is possible to construct an equivalent of:

replicateM p [1..n]

that runs in exponential time (of course) but constant space.

The problem is that this expression is more or less equivalent to the recursion:

badPower 0 _ = pure [] badPower p n = [x:xs | x <- [1..n], xs <- badPower (p-1) n]

So, in the list comprehension, for each selected x, the whole list badPower (p-1) n needs to be re-generated from the start. GHC, sensibly enough, decides to keep badPower (p-1) n around so it doesn't need to be recomputed each time. So, the badPower p n call needs the entire badPower (p-1) n list kept in memory, which already accounts for n^(p-1) elements and exponential memory use, even without considering badPower (p-2) n, etc.

If you just flip the order of the implicit loops around:

goodPower 0 _ = pure [] goodPower p n = [x:xs | xs <- goodPower (p-1) n, x <- [1..n]]

That fixes the problem. Even though the list goodPower (p-1) n is "big", we take it's first element, use it n times for each value of x and then can discard it and move to the next element. So, goodPower (p-1) n can be garbage collected as it's used.

Note that goodPower generates the elements in a different order than badPower, with the first coordinate of the lists varying fastest, instead of the last. (If this matters, you can map reverse $ goodPower .... While reverse is "slow", it's only being applied to short lists here.)

Anyway, the following program runs (practically) forever, but does so in constant space:

power :: Int -> [a] -> [[a]] power 0 _ = [[]] power p lst = [x:xs | xs <- power (p-1) lst, x <- lst ] main = do print $ length (power 15 [1..11])
<h3>Answer2:</h3>
replicateM :: Applicative m => Int -> m a -> m [a]

When 'm' is [], monad join implementation will make replicateM build all permutations of n elements from the list elements. The number of such permutations is written P(n,k), and is equal to n!/(n-k)!. This is where the exponential growth come from.

来源:https://stackoverflow.com/questions/61875763/haskell-running-out-of-memory-with-finite-lists

Recommend

  • haskell running out of memory with finite lists
  • Is there a Python library to list primes?
  • Sum the content of 2 list in Groovy
  • ValueError: could not convert string to float in Pyspark
  • unable to show username in angular
  • How can I create a .swift file for my new .sks file?
  • Asdocs seems unable to find embedded assets
  • identify cash on delivery is availble or not using zip/postal code check on product view page in mag
  • Image gets distorted sometime while uploading
  • Using .Fortran() from R package with error saying function not available
  • Excel: search if a specific text exists in a column
  • Cancel a long task that's managed by a web service
  • Dart HttpClient with Basic Authentication issues after flutter upgrade
  • Azure function C#: Create or replace document in cosmos db on HTTP request
  • How to display or get an image from Firebase storage
  • Byte Array to *Signed* Int
  • How to use Sanitize on HTML Entity
  • Insert in Word bookmarks - Open XML SDK
  • Fork and Join with Amazon Lambda
  • Split an Array into 3 arrays [duplicate]
  • How do I add a trailing slash for Django MPTT-based categorization app?
  • Calling UDF on Dataframe with Serialization Issue
  • Getting CKEditor to work with Flask Admin
  • Rust lifetime error
  • Python ctypes: Prototype with LPCSTR [out] parameter
  • How to move to lines with the same indentation in Visual Studio Code
  • How do I set the logging properties in a spring java configuration?
  • Django REST framework - HyperlinkedRelatedField with additional parameter
  • Unable to run testNG tests from maven
  • JQuery Mobile Ajax Navigation in Single-Page Template
  • Facebook Error (#200) The user hasn't authorized the application to perform this action (PHP)
  • How to load dynamic images in custom ListView
  • What is the difference between dynamically creating a script tag and statically embed a script tag?
  • Year over Year Stats from a Crossfilter Dataset
  • Is there a better way for handling SpatialPolygons that cross the antimeridian (date line)?
  • Google Spreadsheet Script to Blink a range of Cells
  • How can I ssh into a server that requires 2 password authentication using python's paramiko mod
  • how to snap two objects in runtime in unity?
  • Another “Cannot make static reference…” Question
  • How to mutate multiple variables without repeating codes?