kumbaLakAyi kaLLanalla

This code ¹ was written to solve a problem from ²

It’s a simple puzzle which just involved repeated iterations.

The puzzle

THE SECOND TALE OF ABDUL THE JEWELER

“That was also clever!” said the king, after Scheherazade explained the right answer. “Tell me another!”

“Well,” replied Scheherazade, “one night a thief stole into Abdul’s shop—”

“He should be drawn and quartered!” interrupted the king.

“True, Your Majesty,” replied Scheherazade, “but, to get on with my story, the thief joyfully came across a pile of diamonds. His first thought was to take them all, but then his conscience bothered him, and he decided to content himself with only half.”

“Hmm!” said the king.

“And so he took half of the diamonds and started to leave the shop.”

“Ho!” said the king.

“But then he thought: ‘I’ll take one more,’ which he did.”

“Hoo!” said the king.

“And so he left the shop, having stolen half the diamonds plus one.”

“Then what happened?” asked the king.

“Strangely enough, a few minutes later, a second thief entered the shop and took half of the remaining diamonds plus one.

Then a third thief entered the shop and took half the remaining diamonds and one more.

Then a fourth thief entered and took half the remainder and one more.

Then a fifth thief entered, but took no diamonds since they were all gone.”

“So what is the problem?” asked the king.

“The problem,” she said, “is how many diamonds were in the pile to start with?”

“Now, how should I know?”

“It’s not difficult to figure out,”

she replied.

How many diamonds were in the pile?

TWO OTHER VERSIONS

“There are two other versions of the story,” said Scheherazade.

“According to a second version, each of the first four thieves took half of what he found plus two, instead of plus one, and again the fifth thief found none.

According to this version, how many diamonds were originally in the pile?

“The third version is the same as the second, except that the fifth thief found one diamond.

If this version is correct, then how many diamonds did the first thief find?”

The trace

While discussing this with a friend, there was some back and forth between version 1, 2 and 3. I went through a manual trace of version 1 while explaining it to my friend which I show here.

Before t1 : X
t1 takes X/2 + 2 leaving behind X - (X/2 + 2) = X/2 -2
After t1: X/2 − 2 = at₁
t2 finds at₁ and takes at₁/2 + 2 leaving behind at₁/2 − 2
at₂ = at₁/2 − 2
at₃ = at₂/2 − 2
at₄ = at₃/2 − 2
T₅ found 1. i.e. at₄ = 1
at₃ = (1 + 2) * 2
at₃ = 6
at₂ = (6 + 2) * 2
at₂ = 16
at₁ = (16 + 2) * 2
at₁ = 36
X = (36 + 2) * 2
X = 76

The output

There are all variations of the same problem. So I thought this one would be a simple one to code - so that the variations can be parametrized. I never ended up parameterizing since that exploration led somewhere else as the rest of the write up shows.

Here’s the output:

ghc ಕಳ್ಳ.hs 
[1 of 2] Compiling Main             ( ಕಳ್ಳ.hs, ಕಳ್ಳ.o )
[2 of 2] Linking ಕಳ್ಳ

[nix-shell:~/code/ettuge/src/main/haskell]$ ./ಕಳ್ಳ 
76

https://x.com/vishwasms/status/1596565950534254592

[76,36,16,6,1]

Before diving too deep into this haskell code, if you do not know how to read haskell type signatures, I would suggest reading ³.

If you do read haskell reasonably, you can proceed reading this. For people who know haskell well, there’s nothing new here other than true unicode related limitations at the fag end.

The description of the code from Copilot

The file ¹ is a Haskell script with comments and function names in Kannada. Below is a detailed explanation of the code:

Imports:

import Data.Typeable

Functions:

ಎಡಬಲ: Equivalent to scanl in Haskell.
ಕಡೆ: Equivalent to last in Haskell.
ಉಲ್ಟ: Equivalent to reverse in Haskell.
ತಲೆ: Equivalent to head in Haskell.
ಎಡಮಡ್ಇಸ್ಉ: Equivalent to foldl in Haskell.
ಮ್ಉದ್ರ್ಇಸ್ಉ: Equivalent to print in Haskell.

Function ಟ್ಆರ್ಚ್: Haskell

ಟ್ಆರ್ಚ್ :: (Num ಅ) => ಅ -> (ಅ -> ಅ) -> ಅ
ಟ್ಆರ್ಚ್ ಸ್ಊರ್ಯ ಬ಼್ಆಟ್ರ್ಇ = ಬ಼್ಆಟ್ರ್ಇ ಸ್ಊರ್ಯ

This function takes a number and a function, then applies the function to the number.

Function ಓಡ್ಇಸ್ಉ: Haskell

ಓಡ್ಇಸ್ಉ :: (Num ಅ) => [ಅ -> ಅ] -> ಅ -> ಅ
ಓಡ್ಇಸ್ಉ ಕ್ರ್ಇಯ್ಎ ಚರ =
  let ಉತ್ತರ = ಕಡೆ $ ಎಡಬಲ (ಟ್ಆರ್ಚ್) ಚರ ಕ್ರ್ಇಯ್ಎ in
  ಉತ್ತರ

This function takes a list of functions and a number, then applies the scanl operation followed by last to get the final result.

Function ಹಿನ್ದ್ಎ: Haskell

ಹಿನ್ದ್ಎ :: (Num ಅ) => [(ಅ -> ಅ)] -> [ಅ] -> [ಅ] 
ಹಿನ್ದ್ಎ ಕಳ್ಳನಬ್ಉದ್ದ್ಇ ವಜ್ರಗಳ್ಉ =
  ಉತ್ತರ
  where
  ಆಕಳ್ಳನವಜ್ರಗಳ್ಉ = ತಲೆ ವಜ್ರಗಳ್ಉ
  ಈಕಳ್ಳನವಜ್ರಗಳ್ಉ = ಕಳ್ಳನಬ್ಉದ್ದ್ಇ `ಓಡ್ಇಸ್ಉ` ಆಕಳ್ಳನವಜ್ರಗಳ್ಉ
  ಉತ್ತರ = ಈಕಳ್ಳನವಜ್ರಗಳ್ಉ : ವಜ್ರಗಳ್ಉ

This function takes a list of functions and a list of numbers, applies the functions to the head of the number list, and then prepends the result to the original list.

Function ಮ್ಉಖ್ಯ: Haskell

ಮ್ಉಖ್ಯ :: IO ()
ಮ್ಉಖ್ಯ = do
  let ಕಳ್ಳರಸ್ಅಮ್ಖ್ಯ್ಎ = 5
  let ಕ್ಒನ್ಎಕಳ್ಳನವಜ್ರಗಳ್ಉ = 1
  let ಕಳ್ಳನಬ್ಉದ್ದ್ಇ = ಉಲ್ಟ [(*2),(+2)]
  let ಒನ್ದ್ಉಸಲ = (ಹಿನ್ದ್ಎ ಕಳ್ಳನಬ್ಉದ್ದ್ಇ)
  let ಕಳ್ಳನವಜ್ರಗಳ್ಉ ಚರ _ = ಒನ್ದ್ಉಸಲ ಚರ
  let ಖಜ಼್ಆನ್ಎ = ಎಡಮಡ್ಇಸ್ಉ ಕಳ್ಳನವಜ್ರಗಳ್ಉ [ಕ್ಒನ್ಎಕಳ್ಳನವಜ್ರಗಳ್ಉ] [1..(ಕಳ್ಳರಸ್ಅಮ್ಖ�[...]
  ಮ್ಉದ್ರ್ಇಸ್ಉ $ ತಲೆ ಖಜ಼್ಆನ್ಎ
  ಮ್ಉದ್ರ್ಇಸ್ಉ $ ಖಜ಼್ಆನ್ಎ

This is the main function that sets up initial values, applies transformations, and prints results.

Main Entry Point:

main = ಮ್ಉಖ್ಯ

This sets ಮ್ಉಖ್ಯ as the main function to run when the program executes.

The code uses Kannada for function names and comments, but the logic follows standard Haskell patterns and functions.

Some further probing

explain ಒನ್ದ್ಉಸಲ

The function ಒನ್ದ್ಉಸಲ is defined in the ಮ್ಉಖ್ಯ function in the Haskell script src/main/haskell/ಕಳ್ಳ.hs. It is assigned the result of the ಹಿನ್ದ್ಎ function with ಕಳ್ಳನಬ್ಉದ್ದ್ಇ as its argument. The ಹಿನ್ದ್ಎ function processes a list of functions and a list of numbers, applying the functions to the head of the number list and prepending the result to the original list.

explain ಕಳ್ಳನವಜ್ರಗಳ್ಉ

The function ಕಳ್ಳನವಜ್ರಗಳ್ಉ is defined in the ಮ್ಉಖ್ಯ function within the Haskell script src/main/haskell/ಕಳ್ಳ.hs. It is used to apply transformations to a list of values. Specifically, it is created by calling the ಹಿನ್ದ್ಎ function with ಕಳ್ಳನಬ಼ುದ್ದ್ಇ as the argument. This ಹಿನ್ದ್ಎ function processes a list of functions and a list of numbers, applying the functions to the head of the number list and prepending the result to the original list.

ಖಜ಼್ಆನ್ಎ

The function ಖಜ಼್ಆನ್ಎ in the Haskell script src/main/haskell/ಕಳ್ಳ.hs is created by using the ಎಡಮಡ್ಇಸ್ಉ function (equivalent to foldl in Haskell) on ಕಳ್ಳನವಜ್ರಗಳ್ಉ with initial values [1] and a range from 1 to (ಕಳ್ಳರಸ್ಅಮ್ಖ್ಯ್ಎ - 1). The result is then printed twice.

The background for the code

Although I have grown accustomed to use foldl and curried functions, I struggled a bit to understand scanl.

I was reading the classic “Bananas ..”: ⁴

In other words, I didn’t have issues with catamorphisms. All other forms were outside my regular programming vocabulary. I found an excuse to use scanl to broaden it. Although I can see where I could apply some of the others, I have not found problem domains where I can intuitively come up with hylomorphisms or paramorphisms i.e. I have not understood it well enough.

Admittedly, each time I read the paper I can only get up to these generalizations. The latter half of the paper is inscrutable to me.

At that point in time I didn’t have this handy reference which gives an exact guide on how to use recursion-schemes: ⁵

So I have summarized the first part of the paper using Notebook llm here:

*morphisms

A catamorphism is a function that recursively processes a data structure by breaking it down into smaller components and combining the results of processing those components. For example, the sum function for a list can be defined as a catamorphism that starts with an initial value of 0 and repeatedly adds the head of the list to the accumulated sum until the list is empty.

An anamorphism is a function that generates a data structure from a seed value by repeatedly applying a function to generate new elements until a certain condition is met. For example, the iterate function, which generates an infinite list by repeatedly applying a function to a seed value, can be defined as an anamorphism.

A hylomorphism combines the characteristics of both catamorphisms and anamorphisms. It involves first generating a data structure using an anamorphism and then processing that data structure using a catamorphism. This allows for the creation of more complex functions that can both generate and process data structures.

Paramorphisms are a generalization of primitive recursion and allow for functions that “eat their argument and keep it too”. Unlike catamorphisms, which only provide access to the recursive results, paramorphisms provide access to both the current element and the recursive result. For example, the factorial function can be defined as a paramorphism that multiplies the current number with the factorial of the previous number.

Fold

Going back to copilot:

Explain foldl as a catamorphism

In Haskell, foldl is a catamorphism, which means it deconstructs a data structure and reduces it to a single value. Specifically, foldl processes a list from the left (beginning) to the right (end), applying a binary function to each element and an accumulator. The type signature of foldl is:

foldl :: (b -> a -> b) -> b -> [a] -> b

    (b -> a -> b): A function that takes an accumulator of type b and an element of type a and returns a new accumulator of type b.
    b: The initial accumulator value.
    [a]: The list to be folded.

foldl applies the function to the initial accumulator and the first element of the list, then takes the result and applies the function to it and the next element, and so on until the list is fully reduced to a single value.

Example:

foldl (+) 0 [1, 2, 3, 4]  -- Results in 10

This example sums the numbers in the list [1, 2, 3, 4], starting with an initial accumulator value of 0.

Scanl

Anamorphism

Explain scanl as an anamorphism

In Haskell, scanl is an example of an anamorphism, which means it constructs a data structure from a seed value by repeatedly applying a function. Specifically, scanl processes a list from the left (beginning) to the right (end), applying a binary function to each element and an accumulator, and collects all intermediate accumulator values into a new list.

The type signature of scanl is:

scanl :: (b -> a -> b) -> b -> [a] -> [b]

    (b -> a -> b): A function that takes an accumulator of type b and an element of type a and returns a new accumulator of type b.
    b: The initial accumulator value.
    [a]: The list to be processed.

scanl applies the function to the initial accumulator and the first element of the list, then takes the result and applies the function to it and the next element, and so on, collecting all results into a new list.

Example:

scanl (+) 0 [1, 2, 3, 4]  -- Results in [0, 1, 3, 6, 10]

This example generates a list of the running totals of the numbers in the list [1, 2, 3, 4], starting with an initial accumulator value of 0.

Type signatures of various morphisms

The following type signatures from above are illustrative (contasted with foldl and scanl) :

cata :: (a ->       b  -> b) -> b -> [a] ->  b

foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b

?
scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanr :: (a -> b -> b) -> b -> [a] -> [b]

ana  :: (b -> (a,            b))  ->  b  -> [a]

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

Further reading:
para :: (a -> ([a], b) -> b) -> b -> [a] ->  b
apo  :: (b -> (a, Either [a] b))  ->  b  -> [a]
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b 

Traversable

First off, the l and r in foldr and foldl refer to the associativity of the f applied and not really the direction of the list. foldr and foldl should be applicable to any traversable and not just list.

What’s a traversable?

The type signature of the Traversable type class in Haskell is:

class (Functor t, Foldable t) => Traversable t where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Additionally, there is a related function sequenceA:

sequenceA :: Applicative f => t (f a) -> f (t a)

That would appy to something more generic than list but what are we doing to the traversable.

Applicative

If scanl were an Applicative what would f be?

If scanl were an Applicative, the type f would be the type of the accumulator function applied repeatedly to the elements of the list. The type signature of scanl as an Applicative could be seen as:

scanl :: (Applicative f) => (b -> a -> b) -> b -> [a] -> f [b]

Here, f would represent the applicative context in which the accumulation is performed, allowing for more complex or side-effecting computations during the scan operation.

The state of Indic languages as programming tools

If you came to this section and are interested in kannaDa but not programming with kannaDa you are in the wrong place. See the reference section of ¹⁴: ¹⁵.

On a tangential note, I saw someone use unicode greek characters in haskell and it looked cool. I wondered why can’t I use kannaDa. All attempts of people programming in kannada have been somewhat lame - by using variable renames in imperative languages. It didn’t particularly feel natural.

I always felt that the intrinsic support in haskell and scala to build internal DSLs (Domain Specific Languages) can be tapped to write a more natural looking program: ¹

alt text

So I mostly did renames of functions from the English to Kannada. The higher ordered functions give a very abstract feel. However the keywords being in English do take away some elegance. Changing those requires digging a bit deeper.

¹⁶ has some details on how there are other attempts to do so in Thai with Racket and so on. Fundamentally it covers why shell infrastructure is so bad at dealing with unicode scripts - particularly complex ones like those used for Indic characters.

The gist of the issue was that kannaDa - and likely all indic scripts are not rendered well in standard text based editors and the text looks garbled. Graphical editors do a better job. The GHC preprocessor is better than most in dealing with unicode but barfs when true kannada is written.

This explains the strange combination of consonant + virama + full vowel instead of consonant + vowel modifier which is the standard way to type kannaDa in ¹. Reading this would be tortorous for someone who reads kannaDa. Some consonant + virAma + consonant combinations (ottakSaras) were parsed while others didn’t. I had to debug what set of symbols would be allowed v/s not till I figured out that 3+ unicde combinations with vowels expressed as half-characters were what was causing issues. So I had to use full vowels and add a virAma to the preceding consonant to keep the preprocessor happy. Programming is a very limiting experience due to limited support of unicode on terminal emulators. So programs could fail to compile or link anywhere down the line.

Other languages like Racket may do better. Mainstream languages might do better with unicode support but PLs that don’t support currying and higher order functions don’t make good internal Domain Specific Languages (DSLs).

I would stick to romanized proposals like Eke ¹⁴ with adjustments to capitalization per programming language requirements.

Modern shells deal with capitals, spaces and such well. Nushell ¹⁷, fish are quite good with unicode. E.g. see some scripts in ¹⁸ for parsing kannaDa characters, word counting and generating tables in md format for character combinations.

This is not quite true of all pieces of infrastructure in real word compiler ecosystems. If you actually intend to program in a language using unicode, make sure to validate every part of the ecosystem : UI, Build, Shell, Database, Compiler, Linker, Docker, Nix, etc. LLMs and Text-to-speech may reduce this pain in the medium term for things that don’t need too much precision. LLMs dealing with Indic lanuguages also suffer from paucity of data in comparison to English. It’ll take some time for the infra to be good enough wrt how say a modern IDE, Editor, Dev environment etc is good for a computer programmer well-versed in English and programming language of choice.

The next obvious question would be. Why don’t people design a programming language itself in an Indic language like kannaDa. Table the issues with the ecosystem assuming that unicode support will slowly improve over the years. I have hinted at that possibiliy in ¹⁹. I am not advocating programming in λ calculus. Apparently Church himself couldn’t figure out the formula for the predecessor function. A genius student of his dreamt up a solution when on the dentist chair: ²⁰. I just want to note that there’s no intrinsic magic to English in building a complete PL.

Conversely, just because pANini wrote a generative grammar for Samskxta 2300 years ahead of time ²¹, it doesn’t make Samskxta particularly suited for programming as well. Although having a generative grammar would be a great start to do some automated stuff wrt the language. This is an area where LLMs have far outpaced the value of rule based systems.