Developer notes

Mathematical equivalence of bit shifts

a << b <=> a * (2 ^ b)
a >> b <=> a / (2 ^ b)

Apache Bench

The Apache software foundation offers a lot of cool tools. The one of them is Apache Bench. It gives you ability to test and get benchmarks of handling http requests by your web service. I currently use Ubuntu so to play around I ran next command:


sudo apt-get install apache2-utils

And fed my service to it:


ab -n 100 -c 10 http://127.0.0.1/greet

As a result, you'll get next output:


This is ApacheBench, Version 2.3 <$Revision: 1807734 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/

Benchmarking 127.0.0.1 (be patient).....done


Server Software:        nginx/1.17.6
Server Hostname:        127.0.0.1
Server Port:            80

Document Path:          /greet
Document Length:        10 bytes

Concurrency Level:      10
Time taken for tests:   0.004 seconds
Complete requests:      100
Failed requests:        0
Total transferred:      15300 bytes
HTML transferred:       1000 bytes
Requests per second:    27956.39 [#/sec] (mean)
Time per request:       0.358 [ms] (mean)
Time per request:       0.036 [ms] (mean, across all concurrent requests)
Transfer rate:          4177.08 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:     0    0   0.0      0       0
Waiting:        0    0   0.0      0       0
Total:          0    0   0.0      0       0

Percentage of the requests served within a certain time (ms)
  50%      0
  66%      0
  75%      0
  80%      0
  90%      0
  95%      0
  98%      0
  99%      0
 100%      0 (longest request)

Ruby/Haskell. Left and right folds

Haskell has ample opportunities to work with lists, in particular - left and right fold. For this in the Prelude module there are functions such as foldr - for the right fold and foldl - for the left fold:


foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f ini []     = ini
foldr f ini (x:xs) = f x (foldr f ini xs)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f ini []     = ini
foldl f ini (x:xs) = foldl f (f ini x) xs

For an example of their use let's implement the function evenOnly, which throws out elements from the list that stand in odd places, leaving only even ones. One of the implementations is as follows:


evenOnly :: [a] -> [a]
evenOnly = fst . foldr (\x (y1, y2) -> (y2, x:y1)) ([],[])

To do this, we used the right fold. Consider how Haskell will step by step perform the reductions with the fold of the list [1, 2, 3, 4].
Denote the anonymous function (\ x (y1, y2) -> (y2, x: y1)) by f


{- Right fold of list (steps of reductions):
foldr f ([],[]) 1:2:3:4:[]
~> f 1 (foldr f ([],[]) 2:3:4:[])
~> f 1 (f 2 (foldr f ([],[]) 3:4:[]))
~> f 1 (f 2 (f 3 (foldr f ([],[]) 4:[])))
~> f 1 (f 2 (f 3 (f 4 (foldr f ([],[]) []))))
~> f 1 (f 2 (f 3 (f 4 ([],[]))))
~> f 1 (f 2 (f 3 ([],4:[])))
~> f 1 (f 2 (4:[], 3:[]))
~> f 1 (3:[], 2:4:[])
~> (2:4:[], 1:3:[])
([2,4], [1,3])
-}

Let's change the right fold to the left in this implementation:


evenOnly :: [a] -> [a]
evenOnly = fst . foldl (\(y1, y2) x -> (y2, x:y1)) ([],[])

And also let's look how reductions will be executed step by step.


{- Left fold of list (steps of reductions):
foldl f ([],[]) 1:2:3:4:[]
~> foldl f (f ([],[]) 1) (2:3:4:[])
~> foldl f (f (f ([],[]) 1) 2) (3:4:[])
~> foldl f (f (f (f ([],[]) 1) 2) 3) (4:[])
~> foldl f (f (f (f (f ([],[]) 1) 2) 3) 4) []
~> f (f (f (f ([],[]) 1) 2) 3) 4
~> f (f (f ([],1:[]) 2) 3) 4
~> f (f (1:[],2:[]) 3) 4
~> f (2:[], 3:1:[]) 4
~> (3:1:[], 4:2:[])
([3,1], [4,2])
-}

From these examples we can see how the right and left folds differ. Also note that the implementation of evenOnly through left fold certainly behaves incorrectly, because the order of the "even" values becomes incorrect. Also pay attention to the difference of signatures of anonymous functions passed to the functions foldr and foldl. Now we will try to implement similar functionality on Ruby. First, let's implement the functions foldr and foldl:


def foldr(f, ini, list)
  return ini if list.length == 0
  *xs, x = list
  foldr(f, f.call(x, ini), xs)
end

def foldl(f, ini, list)
  return ini if list.length == 0
  x, *xs = list
  foldl(f, f.call(ini, x), xs)
end

Based on the right fold:


evenOnly = ->(list) { foldr(->(x, ini) { xs, ys = ini; [ys, [x, *xs]] }, [[], []], list).first }

Based on the left fold:


evenOnly = ->(list) { foldl(->(ini, x) { xs, ys = ini; [ys, [x, *xs]] }, [[], []], list).first }

Since the left fold is incorrect (given only for demonstration), we take the right fold as the basis and run our implementation for the test a couple of times:


evenOnly.call([])                              # []
evenOnly.call([1])                             # []
evenOnly.call([1, 2, 3, 4])                    # [2, 4]
evenOnly.call([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) # [2, 4, 6, 8, 10]

Ruby/Haskell. Hoare's partition sort or quick sort. Imperative or functional approach?

Some of these days I had fun with Haskell. I tried to write Hoare's sort in Haskell. For my implementation I used list's filtering by the element that was in the middle of the list:


qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort xs = partitions (xs !! (div ((length xs) - 1) 2)) xs where
  partitions x' xs' =
    qsort (filter (< x') xs') ++ (filter (== x') xs') ++ qsort (filter (> x') xs')

What is the most interesting that using of this kind of filtering allows to write a more intuitive algorithm than a variant with an imperative implementation. For comparison, below we can see implementations in Ruby.

This is a variant of imperative implementation:


def hoaresort(array, first, last)
  i, j = first, last
  x  = array[(i + j) / 2]

  begin
    i += 1 while array[i] < x
    j -= 1 while array[j] > x

    if i <= j
      array[i], array[j] = array[j], array[i] if i < j
      i += 1
      j -= 1
    end
  end while (i <= j)

  hoaresort(array, i, last) if i < last
  hoaresort(array, first, j) if first < j

  # Uncomment next line if you want to return sorted array as result
  # array
end

And next is a variant of functional implementation:


def hoaresort(array)
  return [] if array.length == 0
  
  x = array[(0 + (array.length - 1)) / 2]
  
  hoaresort(array.filter { |v| v < x }) +
    array.filter { |v| v == x } +
      hoaresort(array.filter { |v| v > x })
end

In my opinion the comparison obviously shows us that the functional approach is more clear and understandable.

curl. Basic authentication

Specify the user name and password to use for server authentication:


curl --user <name>:<password> http://www.test.com

If you simply specify the user name, curl will prompt for a password:


curl --user <name> http://www.test.com

Also you can encrypt name and password before sending your curl request:


curl -H "Authorization: Basic <your_token>" http://www.test.com

where <your_token> is being generated like that:


-ne "<name>:<password>" | base64 --wrap 0