WillNess

OK, so here's a short progression of implementations for comparison, for clarity:

 {-# LANGUAGE ViewPatterns #-}
 import Data.Array.Unboxed
 import Data.List (tails, inits)
 import qualified Data.List.Ordered as O     -- package 'data-ordlist'

(\) = O.minus

WillNess

my edit for 
  https://stackoverflow.com/questions/45225142/the-pattern-with-functions-like-bool-either-etc/45238164#45238164
  by https://stackoverflow.com/users/3234959/chi


First, the types you mention are not really GADTs, they are plain ADTs, since the return type of each constructor is always `T a`. A proper GADT would be something like

    data T a where
       K1 :: T Bool  -- not T a

WillNess

7 ?- unionp([1,2,3,4],[3,5,2,6,7],X).
X = [1, 4, 3, 5, 2, 6, 7] ;
false.

8 ?- memberd_t(2,[1,2,3],T).
T = true.

9 ?- unionp([1,2,3,4],[3,5,2,6,7],X).
X = [1, 4, 3, 5, 2, 6, 7] ;
false.

WillNess

-- answer at https://stackoverflow.com/questions/32937621/can-someone-explain-this-lazy-fibonacci-solution
-- by pigworker

Your "Because" is not telling the whole story. You're truncating the lists at "the story so far" and evaluating eagerly, then wondering where the rest comes from. That's not quite to grasp what's really going on, so good question.

What gets computed when you make the definition

    fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)

? Very little. Computation starts once you begin to *use* the list. Lazy computation happens only on demand.

WillNess

Prelude> foldr (\x k-> k . (:) x) id [1..4] []
[4,3,2,1]
Prelude> foldl (\k x-> k . (:) x) id [1..4] []
[1,2,3,4]
Prelude>
Prelude> foldr (\x r-> (:) x r) [] [1..4]
[1,2,3,4]
Prelude> foldl (\r x-> (:) x r) [] [1..4]
[4,3,2,1]
Prelude>

WillNess

ps = concat $ scanl (\a b-> dropWhile (<= last a) b) [2]
            $ map (\(x:xs)-> x:takeWhile (< x*x) xs) 
            $ iterate (\(x:xs)-> minus xs [x*x, x*x+2*x..]) 
            $ [3,5..]

ps = concat $ scanl (\a b-> dropWhile (<= last a) b) [2]
            $ map (\(x:xs)-> x:takeWhile (< x*x) xs) 
            $ iterate (\(x:xs)-> let(a,b)=span(<x*x)xs in (x:a,minus b [x*x, x*x+2*x..])) 
                   -- (\(x:xs)-> span (< x*x) xs |> (x:) *** (`minus`  [x*x, x*x+2*x..])) 
            $ [3,5..]

WillNess

-- correction to answer http://stackoverflow.com/a/4787707/849891
-- answered Jan 24 '11 at 22:00 by Thomas M. DuBuisson

You need a way for the fixpoint to terminate.  Expanding your example, it's obvious it won't finish:

    fix id
    --> let x = id x in x
    --> let x = x in x
    --> let x = x in x
    --> ...

WillNess

-- code from http://stackoverflow.com/a/21427171/849891 by András Kovács
combsOf :: Int -> [a] -> [[a]]
combsOf n _ | n < 1   = [[]]
combsOf n (x:xs)      = combsOf n xs ++ map (x:) (combsOf (n - 1) xs)
combsOf _ _           = []

-- what I meant was this
change :: Int -> [Int] -> [[Int]]
change n xs 
     | n<0 || null xs = []

WillNess

-- http://stackoverflow.com/a/1510186/849891

-- does it change the complexity, where to start from ....?    -- make an empirical observation:

{-# OPTIONS_GHC -O2 #-}

g n = let { 
   svs = takeWhile ((< n).(^2).head) $ sv [2..]; 
   ps = map head svs; 
   qs = map (^2) ps; 

WillNess

;; http://stackoverflow.com/a/20691734/849891  answered Dec 19 '13 at 21:10 
;; by Joshua Taylor

Although there's already an accepted answer, I thought you might appreciate a Scheme 
translation of the [Sheep Trick from _The Pitmanual_][1].  Your code is actually 
quite similar to it already.  Scheme does support `do` loops, but they're not 
particularly idiomatic, whereas named `let`s are much more common, so I've used the 
latter in this code.  As you've noted, choosing the first element as the pivot cause 
perfomance problems if the list is already sorted.  Since you have to traverse the 
list on each iteration, there might be some clever thing you could do to pick the