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

Git. Often used command set

Shows git tree of all commits

git log

Moving around in Git: - destination by:

HEAD^
HEAD^^^
HEAD~
HEAD~3
<branch>^
<branch>~2
<branch>

- or by hash of commit:

fed2da64c0efc5293610bdd892f82a58e8cbc5d8

- commands:

git checkout <destination>
git checkout HEAD~;
git checkout HEAD^2;
git checkout HEAD~2;
git checkout HEAD~^2~2
git branch -f <branch> <destination>
git branch <branch> master^~2

- feature in merge commit

git checkout master^1 # goes to the first ancesstor
git checkout master^2 # goes to the second ancesstor

Creates new feature branch without checking out

git branch <feature-branch-name>
git branch <feature-branch-name> HEAD~

Creates new feature branch and check out

git checkout -b branch <feature-branch-name> HEAD~

Rebasing (target branch ia a current branch)

git rebase <source-branch>

- with hash of commit

git rebase <Commit>

- with interactive mode

git rebase -i HEAD~4

- for rebasing target branch with source branch

git rebase <source-branch> <target-branch>

Reversing changes: - only local

git reset HEAD~1

- for share with remote

git revert HEAD

- only for changing last commit message

git commit --amend

Adds commits (copies) to current branch in given order

git cherry-pick <Commit1>, <Commit2>, ...

Tagging commits

git tag <tag-name>
git describe <place>
OUTPUT: <tag>_<numCommits>_g<hash>

Merging changes (target branch ia a current branch)

git merge <source-branch>

Pulling changes from remote
- in merging way
git pull is equal to git fetch; git merge origin/master

git pull
git push

git fetch
git merge origin/master
git push

- in rebase way
git pull --rebase is equal to git fetch; git rebase origin/master

git pull --rebase
git push

git fetch
git rebase origin/master
git push

- when source is related to remote and destination to local (if branch doesn't exist it will be created)

git pull origin <source>:<destination>
git pull origin foo is equal to git fetch origin foo; git merge origin/foo
git pull origin bar~1:bugFix is equal to git fetch origin bar~1:bugFix; git merge bugFix

- Remote tracking (when some branches can be linked by origin/master independently of master branch)

git checkout -b foo origin/master
git pull

git checkout -b foo origin/master
git commit
git push

- when branch exists

git branch -u origin/master foo
git branch -u origin/master

git branch -u foo o/master
git commit
git push

Pushing changes to remote

git push origin <place>

- source is related to local and destination to remote (if branch doesn't exist it will be created)

git push origin <source>:<destination>
git push origin master^^:foo
git push origin foo:master

Removes foo branch in remote

git push origin :foo

Adds bar branch in local

git fetch origin :bar