Trading Fish The blog of Hector Castro

Haskell Code Katas: Counting Duplicates

For the past few weeks, I’ve been starting off my days with Haskell flavored code katas from Codewars. Today I started with the kata below and figured it would be a good exercise to walk through my solution.

Write a function that will return the count of distinct case-insensitive alphabetic characters and numeric digits that occur more than once in the input string. The input string can be assumed to contain only alphabets (both uppercase and lowercase) and numeric digits.

To help clarify the specifications for this kata, the Hspec test suite is below:

module Codwars.Kata.Duplicates.Test where

import Codwars.Kata.Duplicates (duplicateCount)
import Data.List (nub)
import Test.Hspec
import Test.QuickCheck

main = hspec $ do
  describe "duplicateCount" $ do
    it "should work for some small tests" $ do
      duplicateCount ""                         =?= 0
      duplicateCount "abcde"                    =?= 0
      duplicateCount "aabbcde"                  =?= 2
      duplicateCount "aaBbcde"                  =?= 2
      duplicateCount "Indivisibility"           =?= 1
      duplicateCount "Indivisibilities"         =?= 2
      duplicateCount ['a'..'z']                 =?= 0
      duplicateCount (['a'..'z'] ++ ['A'..'Z']) =?= 26
    it "should work for some random lists" $ do
      property $ forAll (listOf $ elements ['a'..'z']) $ \x ->
        let xs = nub x
        in duplicateCount (concatMap (replicate 2) xs) =?= length xs
  where (=?=) = shouldBe

Sorting & Grouping

To start things off, we are given the following snippet:

module Codwars.Kata.Duplicates where

duplicateCount :: String -> Int
duplicateCount = undefined

My first step is to figure out how to deal with case-insensitivity. Within Data.Char is toLower, which can be used to map over each character in the input String.

Prelude> x = "aaBbcde"
Prelude> x
"aaBbcde"
Prelude> import Data.Char
Prelude Data.Char> :t toLower
toLower :: Char -> Char
Prelude Data.Char> map toLower x
"aabbcde"

Next, I want to group like characters together. To do that, I need to sort and then group the characters together.

Prelude Data.Char> import Data.List
Prelude Data.Char Data.List> :t sort
sort :: Ord a => [a] -> [a]
Prelude Data.Char Data.List> sort . map toLower $ x
"aabbcde"

The sort doesn’t do very much in this case because the input string was already sorted. Either way, now we can work on grouping like characters with group:

Prelude Data.Char Data.List> :t group
group :: Eq a => [a] -> [[a]]
Prelude Data.Char Data.List> group . sort . map toLower $ x
["aa","bb","c","d","e"]

Home Stretch

Now, how do we go from a list of [Char] to an Int length that can be used for filtering characters that only occur once? filter, with a >1 condition applied to the length, should get us there.

Prelude Data.Char Data.List> z = group . sort . map toLower $ x
Prelude Data.Char Data.List> filter ((>1) . length) z
["aa","bb"]

Here, the . allows us to compose length and >1 together so that both can be applied to the [Char] provided to filter. The result rids the list of any characters that only occur once in the original input.

Lastly, we need the count of distinct characters from the input String that occur more than one, which is as simple as getting the length of the filtered list.

Prelude Data.Char Data.List> f = filter ((>1) . length) z
Prelude Data.Char Data.List> length f
2

Putting it all together, and breaking out some of the pipelined functions into a variable in the where clause, we get the duplicateCount function below.

module Codwars.Kata.Duplicates where

import Data.List (group, sort)
import Data.Char (toLower)

duplicateCount :: String -> Int
duplicateCount = length . filter ((>1) . length) . grouped
  where
    grouped = group . sort . map toLower

Installing Tor on FreeBSD 11

Tor is a piece of free software and an open network that enables anonymous communication. Combined, these two components help defend against various forms of traffic analysis and network surveillance. Trying to re-explain Tor in a comprehensive way is outside the scope of this post, but please read about it via the literature provided by the project site and The Electronic Frontier Foundation (EFF) before installing.

Installation

The first step toward installing Tor on FreeBSD is deciding whether you want to install the precompiled package with pkg, or you want to compile it yourself from the FreeBSD Ports Collection. The tradeoffs between these two approaches are well-explained within the FreeBSD Handbook. I chose the package because customizing the installation configuration beyond the defaults didn’t seem necessary.

With all of that said, from inside a root shell install the Tor package with:

# pkg install tor

Configuration

From there, copy the sample Tor configuration file into its default location and open it inside your editor:

# cp /usr/local/etc/tor/torrc.sample /usr/local/etc/tor/torrc
# vim /usr/local/etc/tor/torrc

Once inside the file, there are three settings that we want to make explicit. All should be commented out by default (SOCKSPort,Log, and Log again), so we simply need to uncomment them. Below is a diff of the changes between the sample and our desired configuration file:

18c18
< SOCKSPort 9050
---
> #SOCKSPort 9050 # Default: Bind to localhost:9050 for local connections.
38c38
< Log notice file /var/log/tor/notices.log
---
> #Log notice file /var/log/tor/notices.log
42c42
< Log notice syslog
---
> #Log notice syslog

The SOCKSPort setting ensures that we’re binding Tor to 127.0.0.1 on its default port of 9050. The two Log settings ensure that notice level log messages are written to a specific log file, as well as syslog.

Now, we can launch Tor using the tor command to see if things are working properly:

% tor
[notice] Tor v0.2.8.9 running on FreeBSD with Libevent 2.0.22-stable, OpenSSL 1.0.2j-freebsd and Zlib 1.2.8.
[notice] Tor cant help you if you use it wrong! Learn how to be safe at https://www.torproject.org/download/download#warning
[notice] Read configuration file "/usr/local/etc/tor/torrc".
[notice] Opening Socks listener on 127.0.0.1:9050
[notice] Parsing GEOIP IPv4 file /usr/local/share/tor/geoip.
[notice] Parsing GEOIP IPv6 file /usr/local/share/tor/geoip6.
[notice] Bootstrapped 0%: Starting
[notice] Bootstrapped 80%: Connecting to the Tor network
[notice] Bootstrapped 85%: Finishing handshake with first hop
[notice] Bootstrapped 90%: Establishing a Tor circuit
[notice] Tor has successfully opened a circuit. Looks like client functionality is working.
[notice] Bootstrapped 100%: Done

Once satisfied, CTRL+C the process so that control is returned to your shell.

Lastly, let’s enable the Tor service so that it starts on its own after the system boots. To achieve that, all we have to do is ensure that /etc/rc.conf contains the following line:

tor_enable="YES"

Afterwards, launch the Tor service through the service manager if you want it running prior to the next boot cycle:

# service tor start

That’s it. You should now have a fully functional installation of Tor running on FreeBSD.

Raft Leader Election in Consul

A small paper reading group has assembled at work. We give ourselves two to three weeks to read a paper, meetup after hours, eat pizza, and discuss it. Our last paper focused on the Raft consensus algorithm, and I was chosen to lead the discussion.

In order to help the impact of Raft hit closer to home, I put together a small demo of Raft’s leader election process using Consul. The demo spins up a three node Consul cluster using containers, then interleaves all of the debug log output filtered with grep for raft. Reading through parts of the Raft paper, you can see how the logging output of HashiCorp’s implementation lines up.

Reading Along

Section 5.2 of the Raft paper focuses on leader election, and starts off with:

When servers start up, they begin as followers.

Sure enough, the first raft filtered logs start with:

$ docker-compose up | grep raft
consul1 | [INFO] raft: Node at 172.17.0.45:8300 [Follower] entering Follower state
consul2 | [INFO] raft: Node at 172.17.0.44:8300 [Follower] entering Follower state
consul3 | [INFO] raft: Node at 172.17.0.43:8300 [Follower] entering Follower state

Next is the the beginning of an election:

If a follower receives no communication over a period of time called the election timeout, then it assumes there is no viable leader and begins an election to choose a new leader.

That corresponds with:

consul1 | [WARN] raft: Heartbeat timeout reached, starting election

Now that the election started, there needs to be a winner:

A candidate wins an election if it receives votes from a majority of the servers in the full cluster for the same term.

Which goes with:

consul1 | [DEBUG] raft: Votes needed: 2
consul1 | [DEBUG] raft: Vote granted. Tally: 1
consul1 | [DEBUG] raft: Vote granted. Tally: 2
consul1 | [INFO] raft: Election won. Tally: 2
consul1 | [INFO] raft: Node at 172.17.0.45:8300 [Leader] entering Leader state

Lastly, AppendEntries is used to communicate the new leader to all other candidates:

While waiting for votes, a candidate may receive an AppendEntries RPC from another server claiming to be leader.

Logs from consul1 show that it is replicating to consul2 and consul3:

consul1 | [INFO] raft: pipelining replication to peer 172.17.0.44:8300
consul1 | [INFO] raft: pipelining replication to peer 172.17.0.43:8300