Through thorns to Haskell (translation). 2/2

The second part of the TRANSFER is a short and hard introduction to Haskell. The first can be found here.

Original here

Damn hard part

')
Congratulations! You got really far away.
And now trash, waste and sodomy will begin :).

If we are like you, you have already moved into a functional style a bit. You understand the advantages that laziness gives by default. But you still do not quite understand how you can write a really useful program. In particular:

What to do with side effects?
Why did you need such a strange syntax for working with input-output (IO)?

Get ready, the answers may not be the easiest.
But the benefits of them will be certain.

03_Hell / 01_IO / 01_progressive_io_example.lhs

We deal with IO

tl; dr :

A typical function that works with IO looks almost like an imperative program:
 f :: IO a f = do x <- action1 action2 x y <- action3 action4 xy 
To assign a value to an object, we use <- .
In this example, the type of expression in each line is IO * ;
action1 :: IO b
action2 x :: IO ()
action3 :: IO c
action4 xy :: IO a
x :: b , y :: c

Several objects have type IO a .
With such objects, you cannot use pure functions.
In order to use pure functions, you will have to do action2 (purefunction x) .

In this section, I will show how to use IO, but not how it works.
You will see how Haskell separates the pure parts of the program from the parts with side effects.

Do not stop, if some details of the syntax will be a little incomprehensible.
We will return to them in the next section.

What do we want to get?

Get a list of numbers from the user. Print their amount

 toList :: String -> [Integer] toList input = read ("[" ++ input ++ "]") main = do putStrLn "   ( ):" input <- getLine print $ sum (toList input)

The behavior of this program should be obvious.
But let's look closely at the types.

 putStrLn :: String -> IO () getLine :: IO String print :: Show a => a -> IO ()

Have you noticed that every expression in the do block is of type IO a ?

 main = do putStrLn " ... " :: IO () getLine :: IO String print Something :: IO ()

Also note the behavior of the <- .

 do x <- something

If something :: IO a , then x :: a .

Important note on using IO . All lines in the do-block should look like one of two ways:

 action1 :: IO a --      a = ()

 value <- action2 --  -- bar zt :: IO b -- value :: b

These two entries correspond to different ways of describing actions. Full awareness of this offer comes at the end of the next section.

03_Hell / 01_IO / 01_progressive_io_example.lhs

03_Hell / 01_IO / 02_progressive_io_example.lhs

Let's take a look at how this program behaves. For example, what happens if a user enters something weird?
We try:

  % runghc 02_progressive_io_example.lhs Enter a list of numbers (separated by comma): foo Prelude.read: no parse

Arrrghghhhh! Devilish error message and program crash!
Then we need to make the first step so that the error message is easy to read.

In order to do this, we must understand that something has gone wrong.
One way is to use the Maybe type.
This type is very often used in Haskell programs.

 import Data.Maybe

What is this thing? Maybe is a type that takes one parameter. Here is its definition:

 data Maybe a = Nothing | Just a

This is a good way to understand if an error occurred while trying to create / calculate a value.
The maybeRead function is a great example of this approach.
This function is similar to the read function (which is very similar to the javascript eval function, which processes a JSON string.),
but if something goes wrong, the result is a Nothing .
And if the result is correct, it will return Just <> .
Do not try to penetrate deeply into this function.
The code in it is of a lower level than read ; .

 maybeRead :: Read a => String -> Maybe a maybeRead s = case reads s of [(x,"")] -> Just x _ -> Nothing

Now that the code has become more readable, let's write a function that does the following:
if the string came in the wrong format, it will return Nothing .
In other cases, for example, for “1,2,3”, it will return Just [1,2,3] .

 getListFromString :: String -> Maybe [Integer] getListFromString str = maybeRead $ "[" ++ str ++ "]"

Now let's test our code using the main function.

 main :: IO () main = do putStrLn "  ,  :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> print (sum l) Nothing -> error "  . ."

In case of an error, we display a nice error message.

In this case, the type of each expression in the do-block of the main function remains as IO a .
The only weird thing is error .
The error msg function simply accepts any type of input ( IO () in our case).

Pay attention to a very important thing - the types of all functions are defined in advance.
There is only one function, with type IO and this: main .
This means that main is not a pure function.
But it uses the pure getListFromString function.
Just by looking at the declared types of functions, we can distinguish pure functions from functions with side effects.

Why are pure functions important?
I may forget some things, but here are three main reasons:

Clean code is much easier to analyze.
Cleanliness protects you from complex reproducible errors due to side effects.
You can calculate pure functions in any order, or even in parallel, without any risk.

For these reasons, you should keep as much code as possible in clean functions.

03_Hell / 01_IO / 02_progressive_io_example.lhs

03_Hell / 01_IO / 03_progressive_io_example.lhs

The next step is to continuously poll the user, until he enters the correct answer.

The first part will remain unchanged:

 import Data.Maybe maybeRead :: Read a => String -> Maybe a maybeRead s = case reads s of [(x,"")] -> Just x _ -> Nothing getListFromString :: String -> Maybe [Integer] getListFromString str = maybeRead $ "[" ++ str ++ "]"

And now we will write a function that requests a list of numbers, and does not exit until it receives a valid list as input.

 askUser :: IO [Integer] askUser = do putStrLn "  ,  :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser

The type of this function is IO [Integer] .
This means that we get the result of the [Integer] using IO actions.
Some people explain it this way:

"This is [Integer] inside IO "

If you want to understand the internal structure of the I / O mechanism, read the next section.
But, in truth, if you just want to use IO, just write a few simple programs and don't forget to think about types.

As a result, our main function turned out to be much simpler:

 main :: IO () main = do list <- askUser print $ sum list

This concludes our introduction to IO . Everything went very quickly. Here are a few things that I want you to remember:

in the do block, each expression must have type IO a .
You have a rather limited set of possible expressions:
getLine , print , putStrLn , etc.
Try to use the purest functions to the maximum.
type IO a means the following - IO action , which returns a result of type a .
IO type represents actions, and IO a is the type of the function.
If you're still interested, read the next section.

A bit of practice, and using IO will not be a problem for you.

Exercises :

Write a program that summarizes all your arguments. Hint: use the getArgs function.

03_Hell / 01_IO / 03_progressive_io_example.lhs

Explain trick with IO

tl; dr :

To distinguish pure functions,
main defined as a function that changes the state of the world
 main :: World -> World 
Functions with this type are guaranteed to have side effects. Look at a typical main function:
 main w0 = let (v1,w1) = action1 w0 in let (v2,w2) = action2 v1 w1 in let (v3,w3) = action3 v2 w2 in action4 v3 w3 
In this example, many temporary values ( w1 , w2 and w3 )
which are used to transfer data to the next action.

We write the bind function or (>>=) . Thanks to bind we no longer need named temporary values.
  main = action1 >>= action2 >>= action3 >>= action4 
Bonus: Haskell has syntax sugar for us:
  main = do v1 <- action1 v2 <- action2 v1 v3 <- action3 v2 action4 v3 

Why do we need such a strange syntax, and what is the type of IO ? For now, it all looks like some kind of magic.

Forget about pure functions for a while. Concentrate on the side effects:

 askUser :: IO [Integer] askUser = do putStrLn "  ,  :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser main :: IO () main = do list <- askUser print $ sum list

At first, this code looks as if written in ordinary imperative language.
Haskell is cool enough to make code with side effects look imperative.
If you wanted, you could create a Haskell while analog.
In real life, when working with IO , the imperative style is more appropriate.

But you probably noticed that the record is somewhat unusual. So we got to a detailed description of the reasons.

In most languages, the state of the world can be represented as a large implicit global variable. This implicit variable is accessible from anywhere in your program. For example, you can write / read from a file in any function. On the other hand, the presence or absence of a file can be considered as different states of the world.

In Haskell, the state of the world is explicit. We clearly say that the main function can potentially change the state of the world. And its type will look something like this:

 main :: World -> World

But this variable is not available to all functions.
Functions working with this variable are not clean.
Functions that do not use it are clean (there are dangerous exceptions to this rule. But in real programs you will not need it. Unless in the case of deep debugging).

Haskell believes that the world is an input parameter to the main function.
But the real type of this function is more like

 main :: World -> ((),World)

(For those who are interested, the type of expression is data IO a = IO {unIO :: State# RealWorld -> (# State# RealWorld, a #)} . All # are related to optimization, and in the example I swapped several fields. But in general, the idea has not changed.)

Type () is an empty type.
Emptiness.

Let's rewrite our function, not forgetting about:

 main w0 = let (list,w1) = askUser w0 in let (x,w2) = print (sum list,w1) in x

First, all functions with side effects must be of a certain type:

 World -> (a,World)

Where a is the type of result.
For example, the getChar function should be of type World -> (Char,World) .

Another unobvious thing is the order of computing functions.
In Haskell, if you try to calculate fab , you will have several options:

calculate a , then b then fab
first calculate b , then a and finally fab .
parallel to calculate a and b and then fab

Since the language is functionally pure - such tricks are real.

If you now look at the function main, it is obvious that the first line should be calculated earlier than the second, because the first line, calculate the parameter for the second.

This trick works great.
At each step of the calculation, the compiler will pass a pointer to the new modified world.
Under the hood, print works like this:

print something on the screen
change world id
return as result ((),__) .

Now the main looks just awful. Let's do the same with the askUser function:

 askUser :: World -> ([Integer],World)

Before

 askUser :: IO [Integer] askUser = do putStrLn "  :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser

After

 askUser w0 = let (_,w1) = putStrLn "Enter a list of numbers:" in let (input,w2) = getLine w1 in let (l,w3) = case getListFromString input of Just l -> (l,w2) Nothing -> askUser w2 in (l,w3)

Looks like, but ugly. Just look at these clumsy w* variables.

The lesson we learned is that the naive implementation of I / O in a functionally pure language looks terrible.

Fortunately, there is a more direct approach to solving this problem. We see the pattern. Each line is represented as:

 let (y,w') = action xw in

Even if the first parameter x not needed, the result will be a pair (answer, newWorldValue) . Each f function must have a type similar to:

 f :: World -> (a,World)

Moreover, we also noticed that the use of these functions looks very similar:

 let (y,w1) = action1 w0 in let (z,w2) = action2 w1 in let (t,w3) = action3 w2 in ...

Each action can take on input from zero to n parameters. And, in particular, each action can take as input the result of the previous line.

For example, we could write:

 let (_,w1) = action1 x w0 in let (z,w2) = action2 w1 in let (_,w3) = action3 xz w2 in ...

And, of course, actionN w :: (World) -> (a,World) .

IMPORTANT! There are only two patterns that are worth paying attention to:
 let (x,w1) = action1 w0 in let (y,w2) = action2 x w1 in 
and
 let (_,w1) = action1 w0 in let (y,w2) = action2 w1 in 

And now there will be a small trick.
We will make the variable that stores the state of the world disappear. We will bind two strings. To do this, write the function bind .
Her type looks strange at first:

 bind :: (World -> (a,World)) -> (a -> (World -> (b,World))) -> (World -> (b,World))

Don't forget that (World -> (a,World)) is the type for IO action.
Let's rename it for simplicity:

 type IO a = World -> (a, World)

A couple of examples:

 getLine :: IO String print :: Show a => a -> IO ()

getLine is an IO action that takes the world as a parameter and returns a pair (String,World) . You could say the type of getLine would be an IO String .
We can also perceive it as an IO action, which will return to us the String “enclosed inside the IO”.

The print function is also quite interesting. It takes a parameter as input, which it displays later. But in fact, it takes two parameters. The first parameter is the value that will be displayed, the second is the state of the world. As a result, it returns a pair ((),World) . That is, it changes the state of the world, but does not return any data.

This type will allow us to simplify the type definition for the bind function:

 bind :: IO a -> (a -> IO b) -> IO b

bind takes 2 IO actions as arguments and returns another IO action.

Now let's refresh important patterns. The first was:

 let (x,w1) = action1 w0 in let (y,w2) = action2 x w1 in (y,w2)

Pay attention to the types:

 action1 :: IO a action2 :: a -> IO b (y,w2) :: IO b

Looks familiar, isn't it?

 (bind action1 action2) w0 = let (x, w1) = action1 w0 (y, w2) = action2 x w1 in (y, w2)

The basic idea is to hide the World parameter with this function. Go! Here is approximately what we want to get:

 let (line1,w1) = getLine w0 in let ((),w2) = print line1 in ((),w2)

And now, use the bind function:

 (res,w2) = (bind getLine (\l -> print l)) w0

Since print is of type (World -> ((),World)) , we know that res = () (null type).
If you don’t see any special street magic here, try writing a three-line program.

 let (line1,w1) = getLine w0 in let (line2,w2) = getLine w1 in let ((),w3) = print (line1 ++ line2) in ((),w3)

Which is similar to the following:

 (res,w3) = bind getLine (\line1 -> bind getLine (\line2 -> print (line1 ++ line2)))

And now noticed?
Yes, no more World time variables!
This is MA . Gi . I

But we can use a different syntax.
Let's replace bind with (>>=) .
(>>=) is an infix function, the same as
(+) ; remind 3 + 4 ⇔ (+) 3 4

 (res,w3) = getLine >>= \line1 -> getLine >>= \line2 -> print (line1 ++ line2)

Ho ho ho! Happy New Year everyone! Haskell has syntactic sugar for us:

 do x <- action1 y <- action2 z <- action3 ...

Can be replaced by:

 action1 >>= \x -> action2 >>= \y -> action3 >>= \z -> ...

You can use x in action2 and x with y in action3 .

But what about strings that don't use <- ?
Easy! We have a blindBind function:

 blindBind :: IO a -> IO b -> IO b blindBind action1 action2 w0 = bind action (\_ -> action2) w0

I did not specifically simplify this expression.
Of course, if we want to make the code easier, we can use the operator (>>) .

And thus

 do action1 action2 action3

Turns into

 action1 >> action2 >> action3

By the way, here is another rather useful feature:

 putInIO :: a -> IO a putInIO x = IO (\w -> (x,w))

This is the standard way to push pure values into the “IO context”.
Usually putInIO is called return .
This function name is very confusing when learning Haskell. return very different from analogues in other languages.

03_Hell / 01_IO / 21_Detailled_IO.lhs

Finally, let's rewrite our example:

 askUser :: IO [Integer] askUser = do putStrLn "  ,  :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser main :: IO () main = do list <- askUser print $ sum list

Can be rewritten as:

 import Data.Maybe maybeRead :: Read a => String -> Maybe a maybeRead s = case reads s of [(x,"")] -> Just x _ -> Nothing getListFromString :: String -> Maybe [Integer] getListFromString str = maybeRead $ "[" ++ str ++ "]" askUser :: IO [Integer] askUser = putStrLn "  ,  :" >> getLine >>= \input -> let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser main :: IO () main = askUser >>= \list -> print $ sum list

Now you can compile this code to make sure that it works.

And now, let's imagine what it would all look like without (>>) and (>>=) .

03_Hell / 01_IO / 21_Detailled_IO.lhs

03_Hell / 02_Monads / 10_Monads.lhs

Monads

And now let's reveal the secret secret: IO is a monad .
Using monads means you can use syntax sugar do notations.
But the most important thing is a design pattern that will allow you to write cleaner and more understandable code.

Important note :

Monads are not necessarily related to side effects!
There are many pure monads.
The essence of monads - in the composition of calculations

In terms of the Haskell language, Monad is a type class.
To become an instance of this class, you need to define functions (>>=) and return .
The function (>>) will be created automatically based on (>>=) .
Here is the (almost complete) definition of the Monad class:

 class Monad m where (>>=) :: ma -> (a -> mb) -> mb return :: a -> ma (>>) :: ma -> mb -> mb f >> g = f >>= \_ -> g --         --         fail :: String -> ma fail = error

Remarks:
the class keyword is not what you think.
The class in Haskell is not a class from OOP.
A class in Haskell is more like an interface in Java or C #.
It would be better to call it typeclass .
What does a lot of classes mean?
For a type to belong to this class, the type must implement all the functions of the class.
In this particular case, the type m must be a type that can take an argument.
for example, IO a , and also Maybe a , [a] , etc.
To be a useful monad, your function must comply with some laws.
If your function violates these laws, strange things will happen:
 return a >>= k == ka m >>= return == m m >>= (\x -> kx >>= h) == (m >>= k) >>= h 

Maybe is a monad

There are many types that are Monad instances.
The easiest example is Maybe .
If you have a set of Maybe values, you can use monads to work with them. In particular, it can be useful to get rid of nested if..then..else..

Imagine a complex banking operation, you can claim a € 700 bonus only if you have a history of operations without going into a minus.

 deposit value account = account + value withdraw value account = account - value eligible :: (Num a,Ord a) => a -> Bool eligible account = let account1 = deposit 100 account in if (account1 < 0) then False else let account2 = withdraw 200 account1 in if (account2 < 0) then False else let account3 = deposit 100 account2 in if (account3 < 0) then False else let account4 = withdraw 300 account3 in if (account4 < 0) then False else let account5 = deposit 1000 account4 in if (account5 < 0) then False else True main = do print $ eligible 300 -- True print $ eligible 299 -- False

03_Hell / 02_Monads / 10_Monads.lhs

03_Hell / 02_Monads / 11_Monads.lhs

And now we introduce order in this code using Maybe and its Monad entity:

 deposit :: (Num a) => a -> a -> Maybe a deposit value account = Just (account + value) withdraw :: (Num a,Ord a) => a -> a -> Maybe a withdraw value account = if (account < value) then Nothing else Just (account - value) eligible :: (Num a, Ord a) => a -> Maybe Bool eligible account = do account1 <- deposit 100 account account2 <- withdraw 200 account1 account3 <- deposit 100 account2 account4 <- withdraw 300 account3 account5 <- deposit 1000 account4 Just True main = do print $ eligible 300 -- Just True print $ eligible 299 -- Nothing

03_Hell / 02_Monads / 11_Monads.lhs

03_Hell / 02_Monads / 12_Monads.lhs

Not bad, but you can do even better:

 deposit :: (Num a) => a -> a -> Maybe a deposit value account = Just (account + value) withdraw :: (Num a,Ord a) => a -> a -> Maybe a withdraw value account = if (account < value) then Nothing else Just (account - value) eligible :: (Num a, Ord a) => a -> Maybe Bool eligible account = deposit 100 account >>= withdraw 200 >>= deposit 100 >>= withdraw 300 >>= deposit 1000 >> return True main = do print $ eligible 300 -- Just True print $ eligible 299 -- Nothing

So, we proved that monads can make our code more elegant.
Generally speaking, this use of Maybe will work in most imperative languages.
This is a fairly natural design.

Important note:

The first calculation, the result of which is Nothing will stop all further calculations.
This means that not all code will be executed.
And this optimization is available to you absolutely free, thanks to the laziness of the language.

You can rewrite this code using the definition (>>=) for Maybe
:

 instance Monad Maybe where (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b Nothing >>= _ = Nothing (Just x) >>= f = fx return x = Just x

The Maybe monad has proven its usefulness even in such a small example. We also saw the use of the IO monad. But there is a more interesting example - lists.

03_Hell / 02_Monads / 12_Monads.lhs

03_Hell / 02_Monads / 13_Monads.lhs

Monad Lists

The list monad allows us to model non-deterministic calculations.
For example:

 import Control.Monad (guard) allCases = [1..10] resolve :: [(Int,Int,Int)] resolve = do x <- allCases y <- allCases z <- allCases guard $ 4*x + 2*y < z return (x,y,z) main = do print resolve

Ma. Gi. I. :

 [(1,1,7),(1,1,8),(1,1,9),(1,1,10),(1,2,9),(1,2,10)]

For the monad of the list, there is also syntactic sugar:

  print $ [ (x,y,z) | x <- allCases, y <- allCases, z <- allCases, 4*x + 2*y < z ]

I will not give a complete list of monads, there are so many of them.
Using monads can simplify many tasks.
In particular, monads are very useful for:

Io
nondeterministic computing
generating pseudorandom numbers,
storage configuration
working with states
...

If you get to this place, congratulations!
Now you know the ~~kung fu~~ monad! (Of course, you will need practice to get used to them. Write a couple of your own. But you have already made a huge step in this direction)

03_Hell / 02_Monads / 13_Monads.lhs

application

This section is not directly related to learning Haskell. We just pay more attention to some details.

04_Appendice / 01_More_on_infinite_trees / 10_Infinite_Trees.lhs

Something more about endless trees

In the section Infinite structures, we have dismantled a pair of simple infinite structures. Unfortunately, our tree has lost two properties:

no duplicates in the tree nodes
ordered tree

In this section we will deal with the first property.
Regarding the second - we will weaken it a little, but we will try to be as close to the ideal as possible.

First, let's create a list of a set of pseudo-random numbers:

 shuffle = map (\x -> (x*3123) `mod` 4331) [1..]

To refresh the memory, let's duplicate the implementation treeFromList

 treeFromList :: (Ord a) => [a] -> BinTree a treeFromList [] = Empty treeFromList (x:xs) = Node x (treeFromList (filter (<x) xs)) (treeFromList (filter (>x) xs))

and treeTakeDepth:

 treeTakeDepth _ Empty = Empty treeTakeDepth 0 _ = Empty treeTakeDepth n (Node x left right) = let nl = treeTakeDepth (n-1) left nr = treeTakeDepth (n-1) right in Node x nl nr

Let's look at the result:

 main = do putStrLn "take 10 shuffle" print $ take 10 shuffle putStrLn "\ntreeTakeDepth 4 (treeFromList shuffle)" print $ treeTakeDepth 4 (treeFromList shuffle)

 % runghc 02_Hard_Part/41_Infinites_Structures.lhs take 10 shuffle [3123,1915,707,3830,2622,1414,206,3329,2121,913] treeTakeDepth 4 (treeFromList shuffle) < 3123 : |--1915 : | |--707 : | | |--206 : | | `--1414 : | `--2622 : | |--2121 : | `--2828 : `--3830 : |--3329 : | |--3240 : | `--3535 : `--4036 : |--3947 : `--4242

Hooray! Earned! But it will only work if you have something to add to the branch.

For example:

 treeTakeDepth 4 (treeFromList [1..])

will run forever.
This is because the code is trying to get the expression head filter (<1) [2..].
But filternot smart enough to understand that the result of the expression will be an empty list.

Nevertheless, this is a good example of what loose programs can do.

Reader Exercise:

Prove the existence of such a number nthat treeTakeDepth n (treeFromList shuffle)will fall into an infinite loop.
Find the upper bound for n.
Prove that there is no such shufflelist, executing which, the program will end.

04_Appendice / 01_More_on_infinite_trees / 10_Infinite_Trees.lhs

04_Appendice / 01_More_on_infinite_trees / 11_Infinite_Trees.lhs

Davate is slightly modified
treeFromListand shufflein order to get rid of this problem.

The first problem is the lack of random numbers in our implementation shuffle.
We generated only 4331different numbers.
Improve our function shuffle.

 shuffle = map rand [1..] where rand x = ((px) `mod` (x+c)) - ((x+c) `div` 2) px = m*x^2 + n*x + o -- some polynome m = 3123 n = 31 o = 7641 c = 1237

This version of the function is good because (I sincerely hope) has no upper and lower bounds on the values. But the improvements in shuffle are not enough to avoid an endless loop.

Strictly speaking, we cannot say if the list is empty filter (<x) xs.
To solve this problem, I’ll break our binary tree implementation a bit. In the new implementation for some nodes the following condition will not be met:

Any element of the left (or right) must be strictly less (or greater) than the value in the root of the tree.

In this case, the tree will remain almost orderly. Moreover, at the stage of creating a tree, we will ensure the uniqueness of the nodes.

In the new version, treeFromListwe just replaced it filterwith safefilter.

 treeFromList :: (Ord a, Show a) => [a] -> BinTree a treeFromList [] = Empty treeFromList (x:xs) = Node x left right where left = treeFromList $ safefilter (<x) xs right = treeFromList $ safefilter (>x) xs

The function is safefilteralmost identical filterbut does not fall into an infinite loop when processing infinite trees. If she cannot find a suitable element in 10,000 steps, she interrupts the search.

 safefilter :: (a -> Bool) -> [a] -> [a] safefilter fl = safefilter' fl nbTry where nbTry = 10000 safefilter' _ _ 0 = [] safefilter' _ [] _ = [] safefilter' f (x:xs) n = if fx then x : safefilter' f xs nbTry else safefilter' f xs (n-1)

Let's launch the program and rejoice:

 main = do putStrLn "take 10 shuffle" print $ take 10 shuffle putStrLn "\ntreeTakeDepth 8 (treeFromList shuffle)" print $ treeTakeDepth 8 (treeFromList $ shuffle)

You may have noticed that the delay between the mappings of different values is not the same.
This comes because Haskell computes each value as needed.
In this case, the need comes at the time of displaying the number on the screen.

Even if you increase the search depth from 8to 100, the
function will work, and it will not devour all the RAM!

Reader Exercise:

Even for large values deepand nbTry, the function works fine. But in the worst case, we can expect an exponential growth.
Find the worst possible list option for treeFromList.
hint : think about ( [0,-1,-1,....,-1,1,-1,...,-1,1,...]).

At first I tried to implement safefilteras follows:

 safefilter' fl = if filter f (take 10000 l) == []
                  then []
                  else filter fl

, .

, shuffle .
, , 100% .

(, safefilter' )
f
treeFromList' shuffle. .

 treeFromList' [] n = Empty treeFromList' (x:xs) n = Node x left right where left = treeFromList' (safefilter' (<x) xs (fn) right = treeFromList' (safefilter' (>x) xs (fn) f = ???

04_Appendice/01_More_on_infinite_trees/ 11_Infinite_Trees.lhs

( , )

Thank /r/haskellu
/r/programming.
Your comments are invaluable.

In particular, I want to thank Emm a thousand times for the time spent on correcting my English text. Thank's man.

Source: https://habr.com/ru/post/153383/

All Articles