Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You don't generally want <em>tail-recursion</em> in Haskell. What you do want, is <em>productive corecursion</em> (see also <a href="https://softwareengineering.stackexchange.com/a/196827/58561">this</a>), describing what in <a href="http://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs" rel="nofollow noreferrer">SICP</a> is called an <em>iterative process</em>.</p> <p>You can fix the <em>type inconsistency</em> in your function by enclosing initial input in a list. In your example</p> <pre><code>[1, 2, 3, 4, 5] -&gt; [[1, 3, 4], [2, 5]] -&gt; [[1, 3], [4], [2], [5]] </code></pre> <p>only the first arrow is inconsistent, so change it into</p> <pre><code>[[1, 2, 3, 4, 5]] -&gt; [[1, 3, 4], [2, 5]] -&gt; [[1, 3], [4], [2], [5]] </code></pre> <p>which illustrates the process of iteratively applying <code>concatMap splitList1</code>, where</p> <pre><code> splitList1 xs | null $ drop 1 xs = [xs] | magic a b &gt; 0 = [a,b] -- (B) | otherwise = [xs] where (a,b) = splitSomeHow xs </code></pre> <p>You want to stop if no <code>(B)</code> case was fired at a certain iteration. </p> <p>(edit: removed the intermediate version)</p> <p>But it is much better to produce the portions of the output that are ready, as soon as possible:</p> <pre><code>splitList :: [Int] -&gt; [[Int]] splitList xs = g [xs] -- explicate the stack where g [] = [] g (xs : t) | null $ drop 1 xs = xs : g t | magic a b &gt; 0 = g (a : b : t) | otherwise = xs : g t where (a,b) = splitSomeHow xs -- magic a b = 1 -- splitSomeHow = splitAt 2 </code></pre> <p>Don't forget to compile with <code>-O2</code> flag.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow can I convert this binary recursive function into a tail-recursive form?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USWill Ness
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis solution is very aware of Haskell conventions that I do not normally use but should--right down to the Either types. My question is, tail recursion and corecursion are obviously very similar, even as a subset of the other to an extent. Which is better practice in Haskell? The Haskell community seems to favor tail recursion to bypass any stack size overflows, while this solution seems to be only very loosely recursive (the until statement hints of a "while" type of algorithm). Which should be standard practice in this case (to best avoid thunk build-ups)?
      singulars
      1. PO
      1. USuser1104160
    2. CO`Either` is nothing special; I just had to tag list element with "process/do not process further" tags. We could use `(0,)` or `(1,)` for that too, although using `Either` seems "cleaner". As for tail recursion, it depends. It is only better if you calculate something as a whole, which can not be calculated by portions - in which case, TR is worse than "guarded recursion"/"corecursion". Whatever the term, the essence is to get iterative, *online* process with minimal stack use that starts producing parts of output as soon as possible. Code here is only a start, first half-step.
      singulars
      1. PO
      1. USWill Ness
    3. CO@user1104160 the key is split: do you have to have the whole input to split, or is something like `splitAt 10` enough (which would consume 10 elements of the input list and return `(a,b)` where `b` is portion of input still not accessed. Now, **your `magic` actually is the key** - it demands the rest of list, `b`. So, the question becomes, does it need all of the rest of the list, or is there some number of elements that is enough, and you can work by portions of input list? If not, there will be big memory use, if the list is big.
      singulars
      1. PO
      1. USWill Ness
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload