We know the type of `id`,

    id :: a -&gt; a

And when we specialize this for `id id`, the *left* copy of `id` has type:

    id :: (a -&gt; a) -&gt; (a -&gt; a)

And then when you specialize this again for the leftmost `id` in `id id id`, you get:

    id :: ((a -&gt; a) -&gt; (a -&gt; a)) -&gt; ((a -&gt; a) -&gt; (a -&gt; a))

So you see each `id` you add, the type signature of the leftmost `id` is twice as large.

Note that types are deleted during compilation, so this will only take up memory in GHC.  It won&#39;t take up memory in your program.

I am working on an android application where I am using `DialogFragment` to display the dialog but its width is very small. How I can make this width to `fill_parent` to it ?


    public class AddNoteDialogFragment extends DialogFragment {
    
    	public AddNoteDialogFragment() {
    		// Empty constructor required for DialogFragment
    	}
    
    	@Override
    	public View onCreateView(LayoutInflater inflater, ViewGroup container,
    			Bundle savedInstanceState) {
    		getDialog().setTitle(getString(R.string.app_name));
    		View view = inflater.inflate(R.layout.fragment_add_note_dialog,
    				container);
    		
    		return view;
    	}
    
    	   
    	@Override
    	public Dialog onCreateDialog(Bundle savedInstanceState) {
    		Dialog dialog = super.onCreateDialog(savedInstanceState);
    
    		// request a window without the title
    		dialog.getWindow().requestFeature(Window.FEATURE_NO_TITLE);
    		    
    		return dialog;
    	}
    }

fragment_add_note_dialog.xml

    &lt;?xml version=&quot;1.0&quot; encoding=&quot;utf-8&quot;?&gt;
    &lt;LinearLayout xmlns:android=&quot;http://schemas.android.com/apk/res/android&quot;
        android:layout_width=&quot;match_parent&quot;
        android:layout_height=&quot;match_parent&quot;
        android:background=&quot;@android:color/white&quot;
        android:orientation=&quot;vertical&quot;
        android:paddingBottom=&quot;@dimen/activity_vertical_margin&quot;
        android:paddingLeft=&quot;@dimen/activity_horizontal_margin&quot;
        android:paddingRight=&quot;@dimen/activity_horizontal_margin&quot;
        android:paddingTop=&quot;@dimen/activity_vertical_margin&quot; &gt;
    
        &lt;EditText
            android:id=&quot;@+id/addNoteEditText&quot;
            android:layout_width=&quot;match_parent&quot;
            android:layout_height=&quot;wrap_content&quot;
            android:gravity=&quot;top&quot;
            android:hint=&quot;@string/clock_enter_add_note&quot;
            android:imeOptions=&quot;actionDone&quot;
            android:inputType=&quot;textCapSentences|textMultiLine&quot;
            android:lines=&quot;5&quot; /&gt;
    
        &lt;Button
            android:id=&quot;@+id/submit&quot;
            android:layout_width=&quot;match_parent&quot;
            android:layout_height=&quot;wrap_content&quot;
            android:layout_marginTop=&quot;10dp&quot;
            android:background=&quot;@drawable/login_button&quot;
            android:text=&quot;@string/submit_button&quot;
            android:textColor=&quot;@android:color/white&quot; /&gt;
    
    &lt;/LinearLayout&gt;

[![][1]][1]

  [1]: http://i.stack.imgur.com/M1htQ.png

How to make DialogFragment width to Fill_Parent

Using JVM flag 

    -Djavax.net.debug=ssl

is producing a tremendous ammount of logging, the details for every SSL event on the server. Is there anyway to only have it log errors? or possibly there is some better subset of these flags that produce tidier output

    all            turn on all debugging
    ssl            turn on ssl debugging

    The following can be used with ssl:

        record       enable per-record tracing
        handshake    print each handshake message
        keygen       print key generation data
        session      print session activity
        defaultctx   print default SSL initialization
        sslctx       print SSLContext tracing
        sessioncache print session cache tracing
        keymanager   print key manager tracing
        trustmanager print trust manager tracing
        pluggability print pluggability tracing

        handshake debugging can be widened with:
        data         hex dump of each handshake message
        verbose      verbose handshake message printing

        record debugging can be widened with:
        plaintext    hex dump of record plaintext
        packet       print raw SSL/TLS packets

### Further reading
* JavaSE 8: Java Secure Socket Extension (JSSE) Reference Guide: https://docs.oracle.com/javase/8/docs/technotes/guides/security/jsse/JSSERefGuide.html
* JavaSE 8: Debugging SSL/TLS Connections: https://docs.oracle.com/javase/8/docs/technotes/guides/security/jsse/ReadDebug.html
* JavaSE 11: Java Secure Socket Extension (JSSE) Reference Guide: https://docs.oracle.com/en/java/javase/11/security/java-secure-socket-extension-jsse-reference-guide.html

limiting java ssl debug logging

Haskell has an identity function which returns the input unchanged. The definition is simple:

    id :: a -&gt; a
    id x = x

So for fun, this should output `8`:

    f = id id id id id id id id id id id id id id id id id id id id id id id id id id id
    main = print $ f 8

After a few seconds (and about 2 gb of memory according to Task Manager), compilation fails with `ghc: out of memory`. Similarly, the interpreter says `ghci: out of memory`.

Since `id` is a pretty simple function, I wouldn&#39;t expect it to be a memory burden at run time or compile time. What is all the memory being used for?

Why does Haskell&#39;s &quot;do nothing&quot; function, id, consume tons of memory?

Haskell has an identity function which returns the input unchanged. The definition is simple:
<pre><code class="hljs language-bash">id :: a -> a
id x = x
</code></pre>
So for fun, this should output <code>8</code>:
<pre><code class="hljs language-bash">f = id id id id id id id id id id id id id id id id id id id id id id id id id id id
main = print $ f 8
</code></pre>
After a few seconds (and about 2 gb of memory according to Task Manager), compilation fails with <code>ghc: out of memory</code>. Similarly, the interpreter says <code>ghci: out of memory</code>.
Since <code>id</code> is a pretty simple function, I wouldn't expect it to be a memory burden at run time or compile time. What is all the memory being used for?

I have data types defined as:

    data ComitteeView = CommitteeView { committeeId :: CommitteeId
                                      , committeeMembers :: [Person] 
                                      }

    data CommitteesView = CommitteesView { committeeView :: [CommitteeView] }
    
Now, as it stands, I have a Persistent model defined as:

    Person
      name  Text

    Committee
      name  Text

    CommitteePerson
      personId    PersonId
      committeeId CommitteeId

I can pretty easily create a query to populate a CommitteeView, using Esqueleto.  It would go something like this:

    getCommitteeView cid = 
      CommitteeView &lt;$&gt; runDB $ 
        select $
          from (person `InnerJoin` pxc `InnerJoin` committee) -&gt; do
            on  (committee ^. CommitteeId ==. pxc ^. CommitteePersonCommitteeId)
            on  (person ^. PersonId       ==. pxc ^. CommitteePersonPersonId)
            where_ (committee ^. CommitteePersonCommitteeId ==. val cid)
            return person
  
Now, consider the problem of populating `CommitteesView`.  In principle, we get enough data to populate by running subquery in the above query.  Okay, fair enough. Now how can I use &quot;group by Haskell-list&quot; like `group by` in SQL? How can I fold rows so that I can end up with a list of lists of people?

I get the impression that `esqueleto` can&#39;t handle the case as such (i.e., it doesn&#39;t have a combinator that would do it).  And my underlying database obviously doesn&#39;t support Haskell lists as a column.  But, surely, I can&#39;t be the only person to face this issue.  What is an effective strategy?  Folding an n-list of lists into a n-list?  Or running `n+1` queries?  Are there any other options?  

Handling List-types with Esqueleto

There is a well known issue that [we cannot use `forall` types in the `Cont` return type][1].

However it should be OK to have the following definition:

    class Monad m =&gt; MonadCont&#39; m where
        callCC&#39; :: ((a -&gt; forall b. m b) -&gt; m a) -&gt; m a
        shift :: (forall r.(a -&gt; m r) -&gt; m r) -&gt; m a
        reset :: m a -&gt; m a

and then find an instance that makes sense. In [this paper][2] the author claimed that we can implement `MonadFix` on top of `ContT r m` providing that `m` implemented `MonadFix` and `MonadRef`. But I think if we do have a `MonadRef` we can actually implement `callCC&#39;` above like the following:

    --satisfy law: mzero &gt;&gt;= f === mzero
    class Monad m =&gt; MonadZero m where
        mzero :: m a

    instance (MonadZero m, MonadRef r m) =&gt; MonadCont&#39; m where
        callCC&#39; k = do
            ref &lt;- newRef Nothing
            v &lt;- k (\a -&gt; writeRef ref (Just a) &gt;&gt; mzero)
            r &lt;- readRef ref
            return $ maybe v id r
        shift = ...
        reset = ...

(Unfortunately I am not familiar with the semantic of `shift` and `reset` so I didn&#39;t provide implementations for them)

This implementation seems OK for me. Intuitively, when `callCC&#39;` being called, we feed `k` which a function that its own effect is always fail (although we are not able to provide a value of arbitrary type `b`, but we can always provide `mzero` of type `m b` and according to the law it should effectively stop all further effects being computed), and it captures the received value as the final result of `callCC&#39;`.

So my question is:

Is this implementation works as expected for an ideal `callCC`? Can we implement `shift` and `reset` with proper semantic as well?

In addition to the above, I want to know:

To ensure the proper behaviour we have to assume some property of `MonadRef`. So what would the laws a `MonadRef` to have in order to make the above implementation behave as expected?

**UPDATE**

It turn out that the above naive implementation is not good enough. To make it satisfy &quot;Continuation current&quot;

    callCC $\k -&gt; k m === callCC $ const m === m

We have to adjust the implementation to

    instance (MonadPlus m, MonadRef r m) =&gt; MonadCont&#39; m where
        callCC&#39; k = do 
           ref &lt;- newRef mzero
           mplus (k $ \a -&gt; writeRef ref (return a) &gt;&gt; mzero) (join (readRef ref))

In other words, the original `MonadZero` is not enough, we have to be able to combind a `mzero` value with a normal computation without cancelling the whole computation.

**The above does not answer the question, it is just adjusted as the original attempt was falsified to be a candidate. But for the updated version, the original questions are still questions. Especially, `reset` and `shift` are still up to be implemented.**  

           
           

  [1]: https://stackoverflow.com/questions/7178919/how-to-make-callcc-more-dynamic/7180154#7180154
  [2]: http://www.carlssonia.org/ogi/mdo-callcc.pdf

Use MonadRef to implement MonadCont

So far, every monad (that can be represented as a data type) that I have encountered had a corresponding monad transformer, or could have one. Is there such a monad that can&#39;t have one? Or **do all monads have a corresponding transformer?**

By a _transformer `t` corresponding to monad `m`_ I mean that `t Identity` is isomorphic to `m`. And of course that it satisfies the monad transformer laws and that `t n` is a monad for any monad `n`.

I&#39;d like to see either a proof (ideally a constructive one) that every monad has one, or an example of a particular monad that doesn&#39;t have one (with a proof). I&#39;m interested in both more Haskell-oriented answers, as well as (category) theoretical ones.

As a follow-up question, is there a monad `m` that has two distinct transformers `t1` and `t2`? That is, `t1 Identity` is isomorphic to `t2 Identity` and to `m`, but there is a monad `n` such that `t1 n` is not isomorphic to `t2 n`.

(`IO` and `ST` have a special semantics so I don&#39;t take them into account here and let&#39;s disregard them completely. Let&#39;s focus only on &quot;pure&quot; monads that can be constructed using data types.)

Is there a monad that doesn&#39;t have a corresponding monad transformer (except IO)?

**Consider the Object-Oriented Languages:**

Most people coming from an object-oriented programming background, are familiar with the common and intuitive interfaces in various languages that capture the essence of Java&#39;s [**`Collection`**][1] &amp; [**`List`**][2] interfaces. **`Collection`** refers to a  collection of objects which doesn&#39;t necessarily have an natural ordering/indexing. A **`List`** is a collection which has a natural ordering/indexing. These interfaces abstract many library data-structures in Java, as do their equivalent interfaces in other languages, and an intimate understanding of these interfaces are required to work effectively with most library data-structures.

**Transition to Haskell:**

Haskell has a type-class system which acts on types analogously to interfaces on objects. Haskell seems to have a [well designed type-class hierarchy][3] with regard to Functors, Applicative, Monads, etc. when the type regard functionality. They obviously want [correct and well-abstracted type-classes][4]. Yet when you look at many Haskell&#39;s containers ([**`List`**][5],[**`Map`**][6],[**`Sequence`**][7],[**`Set`**][8],[**`Vector`**][9]) they almost all have very similar (or identical) functions, yet aren&#39;t abstracted through type-classes.

**Some Examples:**

 * `null` for testing &quot;emptyness&quot;
 * `length`**/**`size` for element count
 * `elem`**/**`member` for set inclusion
 * `empty` *and/or* `singleton` for default construction
 * `union` for set union
 * `(\\)`**/**`diff` for set difference
 * `(!)`**/**`(!!)` for unsafe indexing (partial function)
 * `(!?)`**/**`lookup` for safe indexing (total function)

If I want to use any of the functions above, but I have imported two or more containers I have to start hiding functions from the imported modules, or explicitly import only the necessary functions from the modules, or qualifying the imported modules. But since all the functions provide the same logical functionality, it just seems like a hassle. If the functions were defined from type-classes, and not separately in each module, the compiler&#39;s type inference mechanics could resolve this. It would also make switching underlying containers simple as long as they shared the type-classes (ie: lets just use a `Sequence` instead of `List` for better random access efficiency).

Why doesn&#39;t Haskell have a **`Collection`** and/or **`Indexable`** type-class(es) to unify &amp; generalize some of these functions?



  [1]: http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html
  [2]: http://docs.oracle.com/javase/7/docs/api/java/util/List.html
  [3]: http://www.haskell.org/wikiupload/d/df/Typeclassopedia-diagram.png
  [4]: http://www.haskell.org/haskellwiki/Functor-Applicative-Monad_Proposal
  [5]: http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-List.html
  [6]: http://hackage.haskell.org/package/containers-0.2.0.1/docs/Data-Map.html
  [7]: http://hackage.haskell.org/package/containers-0.5.5.1/docs/Data-Sequence.html
  [8]: http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.5.5.1/Data-Set.html
  [9]: https://hackage.haskell.org/package/vector-0.9.1/docs/Data-Vector.html

Why is Haskell missing &quot;obvious&quot; Typeclasses

In Scala, algebraic data types are encoded as `sealed` one-level type hierarchies. Example:

&lt;!-- language: haskell --&gt;

    -- Haskell
    data Positioning a = Append
                       | AppendIf (a -&gt; Bool)
                       | Explicit ([a] -&gt; [a]) 

&lt;!-- language: scala --&gt;

    // Scala
    sealed trait Positioning[A]
    case object Append extends Positioning[Nothing]
    case class AppendIf[A](condition: A =&gt; Boolean) extends Positioning[A]
    case class Explicit[A](f: Seq[A] =&gt; Seq[A]) extends Positioning[A]

With `case class`es and `case object`s, Scala generates a bunch of things like `equals`, `hashCode`, `unapply` (used by pattern matching) etc that brings us many of the key properties and features of traditional ADTs.

There is one key difference though – **In Scala, &quot;data constructors&quot; have their own types**. Compare the following two for example (Copied from the respective REPLs).

&lt;!-- language: scala --&gt;

    // Scala

    scala&gt; :t Append
    Append.type
    
    scala&gt; :t AppendIf[Int](Function const true)
    AppendIf[Int]

    -- Haskell

    haskell&gt; :t Append
    Append :: Positioning a

    haskell&gt; :t AppendIf (const True)
    AppendIf (const True) :: Positioning a

---

I have always considered the Scala variation to be on the advantageous side.

After all, **there is no loss of type information**. `AppendIf[Int]` for instance is a subtype of `Positioning[Int]`.

&lt;!-- language: scala --&gt;

    scala&gt; val subtypeProof = implicitly[AppendIf[Int] &lt;:&lt; Positioning[Int]]
    subtypeProof: &lt;:&lt;[AppendIf[Int],Positioning[Int]] = &lt;function1&gt;

In fact, **you get an additional compile time invariant about the value**. (Could we call this a limited version of dependent typing?) 

This can be put to good use – Once you know what data constructor was used to create a value, the corresponding type can be propagated through rest of the flow to add more type safety. For example, Play JSON, which uses this Scala encoding, will only allow you to extract `fields` from `JsObject`, not from any arbitrary `JsValue`.

&lt;!-- language: scala --&gt;

    scala&gt; import play.api.libs.json._
    import play.api.libs.json._
    
    scala&gt; val obj = Json.obj(&quot;key&quot; -&gt; 3)
    obj: play.api.libs.json.JsObject = {&quot;key&quot;:3}
    
    scala&gt; obj.fields
    res0: Seq[(String, play.api.libs.json.JsValue)] = ArrayBuffer((key,3))
    
    scala&gt; val arr = Json.arr(3, 4)
    arr: play.api.libs.json.JsArray = [3,4]
    
    scala&gt; arr.fields
    &lt;console&gt;:15: error: value fields is not a member of play.api.libs.json.JsArray
                  arr.fields
                      ^
    
    scala&gt; val jsons = Set(obj, arr)
    jsons: scala.collection.immutable.Set[Product with Serializable with play.api.libs.json.JsValue] = Set({&quot;key&quot;:3}, [3,4])

In Haskell, `fields` would probably have type `JsValue -&gt; Set (String, JsValue)`. Which means it will fail at runtime for a `JsArray` etc. This problem also manifests in the form of well known partial record accessors. 

**The view that Scala&#39;s treatment of data constructors is wrong has been expressed numerous times** – on Twitter, mailing lists, IRC, SO etc. Unfortunately I don&#39;t have links to any of those, except for a couple - [this answer][1] by Travis Brown, and [Argonaut][2], a purely functional JSON library for Scala.

Argonaut [consciously][3] takes the Haskell approach (by `private`ing case classes, and providing data constructors manually). You can see that the problem I mentioned with Haskell encoding exists with Argonaut as well. (Except it uses `Option` to indicate partiality.)

&lt;!-- language: scala --&gt;

    scala&gt; import argonaut._, Argonaut._
    import argonaut._
    import Argonaut._
    
    scala&gt; val obj = Json.obj(&quot;k&quot; := 3)
    obj: argonaut.Json = {&quot;k&quot;:3}

    scala&gt; obj.obj.map(_.toList)
    res6: Option[List[(argonaut.Json.JsonField, argonaut.Json)]] = Some(List((k,3)))
    
    scala&gt; val arr = Json.array(jNumber(3), jNumber(4))
    arr: argonaut.Json = [3,4]
    
    scala&gt; arr.obj.map(_.toList)
    res7: Option[List[(argonaut.Json.JsonField, argonaut.Json)]] = None


I have been pondering this for quite some time, but still do not understand what makes Scala&#39;s encoding wrong. Sure it hampers type inference at times, but that does not seem like a strong enough reason to decree it wrong. What am I missing?


  [1]: https://stackoverflow.com/questions/25222215/scala-type-based-list-partitioning/25223200#25223200
  [2]: http://argonaut.io/
  [3]: http://mth.io/slides/argonaut/#/18
  [4]: http://mth.io/slides/argonaut/#/

What are the problems with an ADT encoding that associates types with data constructors? (Such as Scala.)

I wrote this small bit of Haskell to figure out how GHC proves that for natural numbers, you can only halve the even ones:

    {-# LANGUAGE DataKinds, GADTs, KindSignatures, TypeFamilies #-}
    module Nat where
    
    data Nat = Z | S Nat
    
    data Parity = Even | Odd
    
    type family Flip (x :: Parity) :: Parity where
      Flip Even = Odd
      Flip Odd  = Even
    
    data ParNat :: Parity -&gt; * where
      PZ :: ParNat Even
      PS :: (x ~ Flip y, y ~ Flip x) =&gt; ParNat x -&gt; ParNat (Flip x)
    
    halve :: ParNat Even -&gt; Nat
    halve PZ     = Z
    halve (PS a) = helper a
      where helper :: ParNat Odd -&gt; Nat
            helper (PS b) = S (halve b)

The relevant parts of core become:

    Nat.$WPZ :: Nat.ParNat &#39;Nat.Even
    Nat.$WPZ = Nat.PZ @ &#39;Nat.Even @~ &lt;&#39;Nat.Even&gt;_N
    
    Nat.$WPS
      :: forall (x_apH :: Nat.Parity) (y_apI :: Nat.Parity).
         (x_apH ~ Nat.Flip y_apI, y_apI ~ Nat.Flip x_apH) =&gt;
         Nat.ParNat x_apH -&gt; Nat.ParNat (Nat.Flip x_apH)
    Nat.$WPS =
      \ (@ (x_apH :: Nat.Parity))
        (@ (y_apI :: Nat.Parity))
        (dt_aqR :: x_apH ~ Nat.Flip y_apI)
        (dt_aqS :: y_apI ~ Nat.Flip x_apH)
        (dt_aqT :: Nat.ParNat x_apH) -&gt;
        case dt_aqR of _ { GHC.Types.Eq# dt_aqU -&gt;
        case dt_aqS of _ { GHC.Types.Eq# dt_aqV -&gt;
        Nat.PS
          @ (Nat.Flip x_apH)
          @ x_apH
          @ y_apI
          @~ &lt;Nat.Flip x_apH&gt;_N
          @~ dt_aqU
          @~ dt_aqV
          dt_aqT
        }
        }
    
    Rec {
    Nat.halve :: Nat.ParNat &#39;Nat.Even -&gt; Nat.Nat
    Nat.halve =
      \ (ds_dJB :: Nat.ParNat &#39;Nat.Even) -&gt;
        case ds_dJB of _ {
          Nat.PZ dt_dKD -&gt; Nat.Z;
          Nat.PS @ x_aIX @ y_aIY dt_dK6 dt1_dK7 dt2_dK8 a_apK -&gt;
            case a_apK
                 `cast` ((Nat.ParNat
                            (dt1_dK7
                             ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N
                             ; Nat.TFCo:R:Flip[0]))_R
                         :: Nat.ParNat x_aIX ~# Nat.ParNat &#39;Nat.Odd)
            of _
            { Nat.PS @ x1_aJ4 @ y1_aJ5 dt3_dKa dt4_dKb dt5_dKc b_apM -&gt;
            Nat.S
              (Nat.halve
                 (b_apM
                  `cast` ((Nat.ParNat
                             (dt4_dKb
                              ; (Nat.Flip
                                   (dt5_dKc
                                    ; Sym dt3_dKa
                                    ; Sym Nat.TFCo:R:Flip[0]
                                    ; (Nat.Flip (dt_dK6 ; Sym dt2_dK8))_N
                                    ; Sym dt1_dK7))_N
                              ; Sym dt_dK6))_R
                          :: Nat.ParNat x1_aJ4 ~# Nat.ParNat &#39;Nat.Even)))
            }
        }
    end Rec }

I know the general flow of casting the types through instances of the Flip type family, but there are some things that I cannot completely follow:

- What&#39;s the meaning of `@~ &lt;Nat.Flip x_apH&gt;_N` ? is it the Flip instance for x? How does that differ from `@ (Nat.Flip x_apH)`? I&#39;m both interested in `&lt; &gt;` and `_N`

Regarding the first cast in `halve`:

- What do `dt_dK6`, `dt1_dK7` and `dt2_dK8` stand for? I understand they are some kind of equivalence proofs, but which is which?
- I understand that `Sym` runs through an equivalence backwards
- What do the `;`&#39;s do? Are the equivalence proofs just applied sequentially?
- What are these `_N` and `_R` suffixes?
- Are `TFCo:R:Flip[0]` and `TFCo:R:Flip[1]` the instances of Flip?



How to read this GHC Core &quot;proof&quot;?

This piece of Haskell code runs *much* slower with `-O`, but `-O` should be [non-dangerous](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/options-optimise.html#optimise-pkgs). Can anyone tell me what happened? If it matters, it is an attempt to solve [this problem](http://tioj.ck.tp.edu.tw/problems/1827), and it uses binary search and persistent segment tree:

    import Control.Monad
    import Data.Array
    
    data Node =
    	  Leaf   Int           -- value
    	| Branch Int Node Node -- sum, left child, right child
    type NodeArray = Array Int Node
    
    -- create an empty node with range [l, r)
    create :: Int -&gt; Int -&gt; Node
    create l r
    	| l + 1 == r = Leaf 0
    	| otherwise  = Branch 0 (create l m) (create m r)
    	where m = (l + r) `div` 2
    
    -- Get the sum in range [0, r). The range of the node is [nl, nr)
    sumof :: Node -&gt; Int -&gt; Int -&gt; Int -&gt; Int
    sumof (Leaf val) r nl nr
    	| nr &lt;= r   = val
    	| otherwise = 0
    sumof (Branch sum lc rc) r nl nr
    	| nr &lt;= r   = sum
    	| r  &gt; nl   = (sumof lc r nl m) + (sumof rc r m nr)
    	| otherwise = 0
    	where m = (nl + nr) `div` 2
    
    -- Increase the value at x by 1. The range of the node is [nl, nr)
    increase :: Node -&gt; Int -&gt; Int -&gt; Int -&gt; Node
    increase (Leaf val) x nl nr = Leaf (val + 1)
    increase (Branch sum lc rc) x nl nr
    	| x &lt; m     = Branch (sum + 1) (increase lc x nl m) rc
    	| otherwise = Branch (sum + 1) lc (increase rc x m nr)
    	where m = (nl + nr) `div` 2
    
    -- signature said it all
    tonodes :: Int -&gt; [Int] -&gt; [Node]
    tonodes n = reverse . tonodes&#39; . reverse
    	where
    		tonodes&#39; :: [Int] -&gt; [Node]
    		tonodes&#39; (h:t) = increase h&#39; h 0 n : s&#39; where s&#39;@(h&#39;:_) = tonodes&#39; t
    		tonodes&#39; _ = [create 0 n]
    
    -- find the minimum m in [l, r] such that (predicate m) is True
    binarysearch :: (Int -&gt; Bool) -&gt; Int -&gt; Int -&gt; Int
    binarysearch predicate l r
        | l == r      = r
        | predicate m = binarysearch predicate l m
        | otherwise   = binarysearch predicate (m+1) r
        where m = (l + r) `div` 2
    
    -- main, literally
    main :: IO ()
    main = do
    	[n, m] &lt;- fmap (map read . words) getLine
    	nodes &lt;- fmap (listArray (0, n) . tonodes n . map (subtract 1) . map read . words) getLine
    	replicateM_ m $ query n nodes
    	where
    		query :: Int -&gt; NodeArray -&gt; IO ()
    		query n nodes = do
    			[p, k] &lt;- fmap (map read . words) getLine
    			print $ binarysearch (ok nodes n p k) 0 n
    			where
    				ok :: NodeArray -&gt; Int -&gt; Int -&gt; Int -&gt; Int -&gt; Bool
    				ok nodes n p k s = (sumof (nodes ! min (p + s + 1) n) s 0 n) - (sumof (nodes ! max (p - s) 0) s 0 n) &gt;= k

(This is exactly the same code with [code review](https://codereview.stackexchange.com/q/85557/24928) but this question addresses another problem.)

This is my input generator in C++:

&lt;!-- language: lang-cpp --&gt;

    #include &lt;cstdio&gt;
    #include &lt;cstdlib&gt;
    using namespace std;
    int main (int argc, char * argv[]) {
        srand(1827);
        int n = 100000;
        if(argc &gt; 1)
            sscanf(argv[1], &quot;%d&quot;, &amp;n);
        printf(&quot;%d %d\n&quot;, n, n);
        for(int i = 0; i &lt; n; i++)
            printf(&quot;%d%c&quot;, rand() % n + 1, i == n - 1 ? &#39;\n&#39; : &#39; &#39;);
        for(int i = 0; i &lt; n; i++) {
            int p = rand() % n;
            int k = rand() % n + 1;
            printf(&quot;%d %d\n&quot;, p, k);
        }
    }

In case you don&#39;t have a C++ compiler available, [this is the result of `./gen.exe 1000`](http://pastebin.com/rDH7zCX9).

This is the execution result on my computer:

&lt;!-- language: none --&gt;

    $ ghc --version
    The Glorious Glasgow Haskell Compilation System, version 7.8.3
    $ ghc -fforce-recomp 1827.hs
    [1 of 1] Compiling Main             ( 1827.hs, 1827.o )
    Linking 1827.exe ...
    $ time ./gen.exe 1000 | ./1827.exe &gt; /dev/null
    real    0m0.088s
    user    0m0.015s
    sys     0m0.015s
    $ ghc -fforce-recomp -O 1827.hs
    [1 of 1] Compiling Main             ( 1827.hs, 1827.o )
    Linking 1827.exe ...
    $ time ./gen.exe 1000 | ./1827.exe &gt; /dev/null
    real    0m2.969s
    user    0m0.000s
    sys     0m0.045s

And this is the heap profile summary:

&lt;!-- language: none --&gt;

    $ ghc -fforce-recomp -rtsopts ./1827.hs
    [1 of 1] Compiling Main             ( 1827.hs, 1827.o )
    Linking 1827.exe ...
    $ ./gen.exe 1000 | ./1827.exe +RTS -s &gt; /dev/null
          70,207,096 bytes allocated in the heap
           2,112,416 bytes copied during GC
             613,368 bytes maximum residency (3 sample(s))
              28,816 bytes maximum slop
                   3 MB total memory in use (0 MB lost due to fragmentation)
                                        Tot time (elapsed)  Avg pause  Max pause
      Gen  0       132 colls,     0 par    0.00s    0.00s     0.0000s    0.0004s
      Gen  1         3 colls,     0 par    0.00s    0.00s     0.0006s    0.0010s
      INIT    time    0.00s  (  0.00s elapsed)
      MUT     time    0.03s  (  0.03s elapsed)
      GC      time    0.00s  (  0.01s elapsed)
      EXIT    time    0.00s  (  0.00s elapsed)
      Total   time    0.03s  (  0.04s elapsed)
      %GC     time       0.0%  (14.7% elapsed)
      Alloc rate    2,250,213,011 bytes per MUT second
      Productivity 100.0% of total user, 83.1% of total elapsed
    $ ghc -fforce-recomp -O -rtsopts ./1827.hs
    [1 of 1] Compiling Main             ( 1827.hs, 1827.o )
    Linking 1827.exe ...
    $ ./gen.exe 1000 | ./1827.exe +RTS -s &gt; /dev/null
       6,009,233,608 bytes allocated in the heap
         622,682,200 bytes copied during GC
             443,240 bytes maximum residency (505 sample(s))
              48,256 bytes maximum slop
                   3 MB total memory in use (0 MB lost due to fragmentation)
                                        Tot time (elapsed)  Avg pause  Max pause
      Gen  0     10945 colls,     0 par    0.72s    0.63s     0.0001s    0.0004s
      Gen  1       505 colls,     0 par    0.16s    0.13s     0.0003s    0.0005s
      INIT    time    0.00s  (  0.00s elapsed)
      MUT     time    2.00s  (  2.13s elapsed)
      GC      time    0.87s  (  0.76s elapsed)
      EXIT    time    0.00s  (  0.00s elapsed)
      Total   time    2.89s  (  2.90s elapsed)
      %GC     time      30.3%  (26.4% elapsed)
      Alloc rate    3,009,412,603 bytes per MUT second
      Productivity  69.7% of total user, 69.4% of total elapsed




Why does this Haskell code run slower with -O?

I&#39;m trying to use the `ghc-mod` vim plugin to do type/syntax checking etc. However, I found that `ghc-mod` always uses full paths of types in the error messages, for example:

    test.hs|71 col 13 error| Couldn&#39;t match type ‘Data.Text.Internal.Text’                                                                                   
    ||                with ‘[GHC.Types.Char]’
    || Expected type: containers-0.5.6.2:Data.Map.Base.Map
    ||                  [GHC.Types.Char]
    ||                  ([(integer-gmp-1.0.0.0:GHC.Integer.Type.Integer,
    ||                     integer-gmp-1.0.0.0:GHC.Integer.Type.Integer)],
    ||                   containers-0.5.6.2:Data.Set.Base.Set
    ||                     integer-gmp-1.0.0.0:GHC.Integer.Type.Integer)
    ||   Actual type: containers-0.5.6.2:Data.Map.Base.Map
    ||                  Data.Text.Internal.Text
    ||                  ([(integer-gmp-1.0.0.0:GHC.Integer.Type.Integer,
    ||                     integer-gmp-1.0.0.0:GHC.Integer.Type.Integer)],
    ||                   containers-0.5.6.2:Data.Set.Base.Set
    ||                     integer-gmp-1.0.0.0:GHC.Integer.Type.Integer)
    || In the second argument of ‘containers-0.5.6.2:Data.Map.Base.map’, namely
    ||   ‘zippedMap’
    || In the second argument of ‘(GHC.Base.$)’, namely
    ||   ‘containers-0.5.6.2:Data.Map.Base.map
    ...

which clutters the screen and it&#39;s very hard for me to find out where went wrong. As comparison, this is the error message for the same file using `ghci`:

    test.hs:71:13:
        Couldn&#39;t match type ‘T.Text’ with ‘[Char]’
        Expected type: M.Map [Char] ([(Integer, Integer)], S.Set Integer)
          Actual type: M.Map T.Text ([(Integer, Integer)], S.Set Integer)
        In the second argument of ‘M.map’, namely ‘zippedMap’
        In the second argument of ‘($)’, namely
          ‘M.map
    ...

which is much cleaner. Is there a way to make `ghc-mod` use short names for the types?

Does GHC-mod have to use full names for types?

Haskell (with the `GHC` compiler) is a [lot faster than you&#39;d expect][1]. Used correctly, it can get close-ish to low-level languages. (A favorite thing for Haskellers to do is to try and get within 5% of C (or even beat it, but that means you are using an inefficient C program, since GHC compiles Haskell to C).) My question is, why?

Haskell is declarative and based on lambda calculus. Machine architectures are clearly imperative, being based on turing machines, roughly. Indeed, Haskell doesn&#39;t even have a specific evaluation order. Also, instead of dealing with machine data types, you make algebraic data types all the time.

Weirdest of all though is higher order functions. You would think that creating functions on the fly, and throwing them around, would make a program slower. [But using higher order functions actually makes Haskell faster.][2] Indeed, it seems that, to optimize Haskell code, you need to make it more elegant and abstract instead of more machine-like. None of Haskell&#39;s more advanced features seem to even *affect* its performance, if they don&#39;t improve it.

Sorry if this is sounding ranty, but here is my question: **Why is Haskell (compiled with GHC) so fast, considering its abstract nature and differences from physical machines?**

Note: The reason I say C and other imperative languages are somewhat similar to Turing Machines (but not to the extent that Haskell is similar to Lambda Calculus) is that in an imperative language, you have a finite number of states (a.k.a. line number), along with a Tape (the ram), such that the state and the current tape determine what to do to the tape. See the Wikipedia entry, [Turing machine equivalents][0], for the transition from Turing Machines to computers.

  [0]: https://en.wikipedia.org/wiki/Turing_machine_equivalents
  [1]: https://wiki.haskell.org/Why_Haskell_matters#The_speed_of_Haskell
  [2]: https://hbtvl.wordpress.com/2015/12/14/efficient-parsing-of-large-text-files-part-4-and-conclusion/

Why is Haskell (GHC) so darn fast?

We are developing a program which receives and forwards &quot;messages&quot;, while keeping a temporary history of those messages, so that it can tell you the message history if requested. Messages are identified numerically, are typically around 1 kilobyte in size, and we need to keep hundreds of thousands of these messages.

We wish to optimize this program for latency: the time between sending and receiving a message must be below 10 milliseconds.

The program is written in Haskell and compiled with GHC. However, we have found that garbage collection pauses are far too long for our latency requirements: over 100 milliseconds in our real-world program.

The following program is a simplified version of our application. It uses a `Data.Map.Strict` to store messages. Messages are `ByteString`s identified by an `Int`. 1,000,000 messages are inserted in increasing numeric order, and the oldest messages are continually removed to keep the history at a maximum of 200,000 messages.

    module Main (main) where

    import qualified Control.Exception as Exception
    import qualified Control.Monad as Monad
    import qualified Data.ByteString as ByteString
    import qualified Data.Map.Strict as Map

    data Msg = Msg !Int !ByteString.ByteString

    type Chan = Map.Map Int ByteString.ByteString

    message :: Int -&gt; Msg
    message n = Msg n (ByteString.replicate 1024 (fromIntegral n))

    pushMsg :: Chan -&gt; Msg -&gt; IO Chan
    pushMsg chan (Msg msgId msgContent) =
      Exception.evaluate $
        let
          inserted = Map.insert msgId msgContent chan
        in
          if 200000 &lt; Map.size inserted
          then Map.deleteMin inserted
          else inserted

    main :: IO ()
    main = Monad.foldM_ pushMsg Map.empty (map message [1..1000000])

We compiled and ran this program using:

    $ ghc --version
    The Glorious Glasgow Haskell Compilation System, version 7.10.3
    $ ghc -O2 -optc-O3 Main.hs
    $ ./Main +RTS -s
       3,116,460,096 bytes allocated in the heap
         385,101,600 bytes copied during GC
         235,234,800 bytes maximum residency (14 sample(s))
         124,137,808 bytes maximum slop
                 600 MB total memory in use (0 MB lost due to fragmentation)

                                         Tot time (elapsed)  Avg pause  Max pause
      Gen  0      6558 colls,     0 par    0.238s   0.280s     0.0000s    0.0012s
      Gen  1        14 colls,     0 par    0.179s   0.250s     0.0179s    0.0515s

      INIT    time    0.000s  (  0.000s elapsed)
      MUT     time    0.652s  (  0.745s elapsed)
      GC      time    0.417s  (  0.530s elapsed)
      EXIT    time    0.010s  (  0.052s elapsed)
      Total   time    1.079s  (  1.326s elapsed)

      %GC     time      38.6%  (40.0% elapsed)

      Alloc rate    4,780,213,353 bytes per MUT second

      Productivity  61.4% of total user, 49.9% of total elapsed

The important metric here is the &quot;max pause&quot; of 0.0515s, or 51 milliseconds. We wish to reduce this by at least an order of magnitude.

Experimentation shows that the length of a GC pause is determined by the number of messages in the history. The relationship is roughly linear, or perhaps super-linear. The following table shows this relationship. ([You can see our benchmarking tests here](https://github.com/jameshfisher/ghc_gc_benchmarks), and [some charts here](https://docs.google.com/spreadsheets/d/1mDXrk8bqPb_nsR__pzHtSxwO8a_6bPVL8hd3Y9lCIm0/edit?usp=sharing).)

    msgs history length  max GC pause (ms)
    ===================  =================
    12500                                3
    25000                                6
    50000                               13
    100000                              30
    200000                              56
    400000                             104
    800000                             199
    1600000                            487
    3200000                           1957
    6400000                           5378

We have experimented with several other variables to find whether they can reduce this latency, none of which make a big difference. Among these unimportant variables are: optimization (`-O`, `-O2`); RTS GC options (`-G`, `-H`, `-A`, `-c`), number of cores (`-N`), different data structures (`Data.Sequence`), the size of messages, and the amount of generated short-lived garbage. The overwhelming determining factor is the number of messages in the history.

Our working theory is that the pauses are linear in the number of messages because each GC cycle has to walk over all the working accessible memory and copy it, which are clearly linear operations.

Questions:

* Is this linear-time theory correct? Can the length of GC pauses be expressed in this simple way, or is the reality more complex?
* If GC pause is linear in the working memory, is there any way to reduce the constant factors involved?
* Are there any options for incremental GC, or anything like it? We can only see research papers. We are very willing to trade throughput for lower latency.
* Are there any ways to &quot;partition&quot; memory for smaller, GC cycles, other than splitting into multiple processes?

Content Type	Original Author	Original Content on Stackoverflow
Question	Ryan	View Question on Stackoverflow
Solution 1 - Haskell	Dietrich Epp	View Answer on Stackoverflow

Why does Haskell's "do nothing" function, id, consume tons of memory?

Haskell Problem Overview

Haskell Solutions

Solution 1 - Haskell

limiting java ssl debug logging

How to make DialogFragment width to Fill_Parent

Attributions