I'm trying to learn how to list comprehension and I'm trying to figure out a way to find all the subsequences of a list but i'm not quite sure how one would go about that. Could anyone help me?

# Haskell – How to find all of the subsequences of a list

haskell

#### Related Solutions

Using `GHC 7.0.3`

, `gcc 4.4.6`

, `Linux 2.6.29`

on an x86_64 Core2 Duo (2.5GHz) machine, compiling using `ghc -O2 -fllvm -fforce-recomp`

for Haskell and `gcc -O3 -lm`

for C.

- Your C routine runs in 8.4 seconds (faster than your run probably because of
`-O3`

) - The Haskell solution runs in 36 seconds (due to the
`-O2`

flag) - Your
`factorCount'`

code isn't explicitly typed and defaulting to`Integer`

(thanks to Daniel for correcting my misdiagnosis here!). Giving an explicit type signature (which is standard practice anyway) using`Int`

and the time changes to**11.1 seconds** - in
`factorCount'`

you have needlessly called`fromIntegral`

. A fix results in no change though (the compiler is smart, lucky for you). - You used
`mod`

where`rem`

is faster and sufficient. This changes the time to**8.5 seconds**. `factorCount'`

is constantly applying two extra arguments that never change (`number`

,`sqrt`

). A worker/wrapper transformation gives us:

```
$ time ./so
842161320
real 0m7.954s
user 0m7.944s
sys 0m0.004s
```

That's right, **7.95 seconds**. Consistently **half a second faster than the C solution**. Without the `-fllvm`

flag I'm still getting `8.182 seconds`

, so the NCG backend is doing well in this case too.

Conclusion: Haskell is awesome.

**Resulting Code**

```
factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
where square = sqrt $ fromIntegral number
isquare = floor square
factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
where
go candidate count
| candidate > sqrt = count
| number `rem` candidate == 0 = go (candidate + 1) (count + 2)
| otherwise = go (candidate + 1) count
nextTriangle index triangle
| factorCount triangle > 1000 = triangle
| otherwise = nextTriangle (index + 1) (triangle + index + 1)
main = print $ nextTriangle 1 1
```

EDIT: So now that we've explored that, lets address the questions

Question 1: Do erlang, python and haskell lose speed due to using arbitrary length integers or don't they as long as the values are less than MAXINT?

In Haskell, using `Integer`

is slower than `Int`

but how much slower depends on the computations performed. Luckily (for 64 bit machines) `Int`

is sufficient. For portability sake you should probably rewrite my code to use `Int64`

or `Word64`

(C isn't the only language with a `long`

).

Question 2: Why is haskell so slow? Is there a compiler flag that turns off the brakes or is it my implementation? (The latter is quite probable as haskell is a book with seven seals to me.)

Question 3: Can you offer me some hints how to optimize these implementations without changing the way I determine the factors? Optimization in any way: nicer, faster, more "native" to the language.

That was what I answered above. The answer was

- 0) Use optimization via
`-O2`

- 1) Use fast (notably: unbox-able) types when possible
- 2)
`rem`

not`mod`

(a frequently forgotten optimization) and - 3) worker/wrapper transformation (perhaps the most common optimization).

Question 4: Do my functional implementations permit LCO and hence avoid adding unnecessary frames onto the call stack?

Yes, that wasn't the issue. Good work and glad you considered this.

- The
*horizontal bar*means that "[above]**implies**[below]". - If there are
*multiple expressions*in [above], then consider them**anded**together; all of the [above] must be true in order to guarantee the [below]. `:`

means**has type**`∈`

means**is in**. (Likewise`∉`

means "is not in".)`Γ`

is usually used to refer to an**environment**or context; in this case it can be thought of as a set of type annotations, pairing an identifier with its type. Therefore`x : σ ∈ Γ`

means that the environment`Γ`

includes the fact that`x`

has type`σ`

.`⊢`

can be read as**proves**or determines.`Γ ⊢ x : σ`

means that the environment`Γ`

determines that`x`

has type`σ`

.`,`

is a way of**including**specific additional assumptions into an environment`Γ`

.

Therefore,`Γ, x : τ ⊢ e : τ'`

means that environment`Γ`

,*with the additional, overriding assumption that*, proves that`x`

has type`τ`

`e`

has type`τ'`

.

As requested: operator precedence, from highest to lowest:

- Language-specific infix and mixfix operators, such as
`λ x . e`

,`∀ α . σ`

, and`τ → τ'`

,`let x = e0 in e1`

, and whitespace for function application. `:`

`∈`

and`∉`

`,`

(left-associative)`⊢`

- whitespace separating multiple propositions (associative)
- the horizontal bar

## Best Solution

If you want access to this functionality, you can use the

`subsequences`

function that is in`Data.List`

.If you want to know how it's implemented, you can check the function's source code, which is available on Hackage.

In this case, it's: