DEV Community: tyrael

Tangible Correctness

tyrael — Mon, 14 Jul 2025 11:07:26 +0000

Testing code is one of the more overlooked yet polarizing aspects of modern software development. It's a pretty hand-wavy subject especially considering most educational material on creating software don't even cover writing effective tests, yet the importance of it is brought up time and time again. This article will try to get more in-depth with writing tests for your code, based on my recent experience as an intern backend developer.

When not to test

It might seem backward but the first important thing to consider about testing is whether or not you have to test the code in the first place. I simply can't agree with testing puritans that enforce 100% unit test coverage, as a lot of these tests end up as being nothing but smoke tests.

Only test code that is yours.

To be specific, only test logic that you yourself have implemented. Writing expectancy tests for libraries and modules that you have imported via your language's package manager is redundant and unnecessary. Even if your test does catch some bug with the library you are using, fixing it will be out of scope for your project (but you should probably file an issue in their GitHub repository). Use trusted external dependencies as trusted external dependencies.

It is very likely that external libraries already have their own tests for their code, so you should not be worrying about creating said tests. Writing tests is always going to be a balance between the cost of the bugs that your tests are checking for and the cost it takes to introduce the test to your code base, and if the bugs cannot be fixed by you, those tests are worthless.

Unless you get reviewed by the number of lines of code you've contributed then you really shouldn't be testing behavior of external dependencies.

Factories, fixtures, and faking

Always try to make your tests themselves modular and parameterized. By creating fixtures, you reduce redundant setup code (which overall lowers the noise and increases readability of your tests), and by parameterizing tests you increase your coverage without drastically increasing your code.

Moreover, factories fall under this same category of modularizing redundant setup code within your tests. Remember, your tests job is to test your code, not create more ceremony.

The factory library that I've had the pleasure of using was factory_boy, for a Django project. In combination with pytest fixtures, writing tests became pretty enjoyable and elegant. Not only can factories be used to generate Model instances for your unit tests, they can also be handy in creating entries in your database for end-to-end testing if you're using some form of Object-Relational Mapping (ORM) for your project.

Lastly, factory_boy interfaces very well with the existing faker library, which made mocking values very easy to do. Mocking data is also very handy as it, again, increases your test coverage without bloating your code. Having a good mechanism for mocking data, via external dependency or in-house generators, can prove to be very handy to make your tests even more reassuring.

Automate tests

Although it might be a bit daunting, it is very worth it to spend a couple of hours setting up some form of automated testing (in my case via GitHub actions). Remember, tests entire purpose is to ensure integrity within your code (especially when changes are introduced), and you simply just can't rely on remembering to run your tests every time you merge a pull request. Not only does this create a layer of security for your pull requests, it also frees you up to isolate your tests freely within your local development environment as you get the reassurance of your automated tests testing everything else.

Use AI

I personally don't use AI generative tools when I'm writing my code, with the sole exception of tests (and creating models, boilerplate-y stuff). The probabilistic properties of AI generated code plays very well into writing tests as it is not unlikely for a human developer to miss certain edge cases in their logic, but not for AI. I have often times found myself thinking "oh right" when reading Copilot's suggested code and that has done nothing but bolster my trust in my tests. Not to mention, it saves you time by letting you "lazily" use your testing suite, I only reach for certain assert methods when I need them so often times I would have Copilot suggest it to me and then that's when I'll read the documentation for it.

Conclusion

Testing is indeed important, but often times not discussed enough. Writing expectancy tests for code has honestly made me feel more confident in being a programmer; it made me tackle topics that I initially had not encountered- just because they were good solutions for testing (a notable example was me writing multi-threading code to create tests that handle race conditions)!

Moreover, there are plenty of ways to increase your test coverage without increasing your code size, namely factories, fixtures, and mocking; and this is effective testing.

You do not have to fully commit to a test-driven development style, as long as you have stable and rigid tests that you can rely on. Good tests serve as a foundation for the rest of your code, and having a good foundation is a sign of a good architecture. And who doesn't want well-architected code?

(This article hasn't even covered the dopamine surge you get from seeing tests go green!)

In defense of `union` and `goto`

tyrael — Sat, 26 Apr 2025 12:45:23 +0000

Like mentioned in my previous video, memory safety has been an issue since the dawn of programming, which is the main reason why an entire category of memory safe languages exist in the first place.

And now, there's currently a big push by the American government, and the FBI in particular, to move away from memory unsafe languages or produce a memory safety roadmap for existing government software that use these aforementioned languages.

Of course, entirely migrating to a different language especially when most of the existing software is written in languages like C/C++, is a monumental task. Which is why many people have taken it into their own hands the responsibility of extending C/C++ to be safer, or entirely memory safe, instead of rewriting their entire codebase.

One of these attempts in particular caught my attention, TrapC.

Undefined behavior

Before even reading the rest of the language spec you are met with its title: "TrapC: Memory Safe C Programming with No UB"

Although I agree that undefined behavior is quite annoying, we must not forget that C's edge on performance hinge on undefined behavior existing! Having to not consider entire branches of logic (i.e. accessing uninitialized arrays, null checking every pointer dereference), lets the compiler perform absolutely heinous optimizations, as long as you don't actually invoke the undefined branches.

This is in theme with the rest of the language's design principles, that is to sacrifice these safety checks for a staggering increase in its efficiency and the ability to get away with the fastest implementation for target architectures. The compiler offloads this responsibility to the programmer.

And if the use case demanded for C in the first place, specifically for realtime software, you should NOT be willing to take that performance hit.

But let's give TrapC the benefit of the doubt that maybe it is worth to do this change for the sake of memory safety.

`union` and `goto`

TrapC removes 2 keywords: 'goto' and 'union', as unsafe and having been widely deprecated from use

Now to say that this change is outrageous is an understatement. It is harmful and outright offensive to the language itself. People who don't know better would actually believe these statements as it comes from the false authority of a language proponent.

Unions have never been deprecated, and goto still has its use cases, such as greatly improving readability and reducing code duplication for errorhandling and escaping nested loops.

"So we tried C, we didn't understand why certain features existed or they weren't necessary for our use case, so we've decided that everyone else also doesn't know how to use it and therefore it shouldn't exist for all other use cases."

In fact, instead of just ragging this completely arrogant change, let's go over how you can properly use these language features, specifically union.

Unions

For those who are unfamiliar, unions are a type construct which holds attributes that share the same memory, the alignment of the union being the largest type in it.

struct IntOrFloatOrBool {
  int n;   // 4 bytes
  float f; // 4 bytes
  bool b;  // 1 byte
};

// [ i i i i ] [ f f f f ] [ b _ _ _ ]
// stored in memory with 12 bytes!

union IntOrFloatOrBool {
  int n;    // 4 bytes
  float f;  // 4 bytes
  bool b;   // 1 byte
};

// [ x x x x ]
// stored in memory with 4 bytes.

You can think of alignment as the size a type assumes. This is mostly influenced by the largest type in a struct, as we cannot store types with differing alignments. Which means our smaller types get padded by garbage data to fulfill the alignment requirements of a struct.

Of course this issue of wasted memory in padding only gets worse with types that have attributes of a bigger size, and when storing them in arrays (which require elements of the same alignment)

struct Foo {
  int bar;      // 4 bytes
  double baz;   // 8 bytes
  bool qux;     // 1 byte
};

/* 
  [ i i i i | _ _ _ _ ] 
  [ d d d d | d d d d ] 
  [ b _ _ _ | _ _ _ _ ]

  stored in 24 bytes! 
  (16 if arranged such that double comes first)
*/

union Foo {
  int bar;      // 4 bytes
  double baz;   // 8 bytes
  bool qux;     // 1 byte
};

/* 
  [ x x x x | x x x x ] 

  stored in 8 bytes!
*/

The arrangement in the struct is not optimized by the compiler because of its volatile nature (its location in memory might be relevant to the context of the program, i.e. embedded systems)

By itself, unions struggle to see any practical application outside of programs that concern themselves with bitwise operations. As it turns out, being able to reinterpret values as other types does offer clever ways of doing bitwise operations.

Tagged unions

But if we really think about it, using a union's field usually entails that we only care about that interpretation for that specific variable. That is, if we define a union type and access an int field, we would only ever want to do operations on it that we could do on an int.

We can name this behavior as unions having an active state. If we access a union as a specific type during an assignment, we would only ever want to access it as that type.

typedef union {
  int rotations;
  float degrees;
} Rotation;

Rotate angle = { .degrees = 0.45f };  // float as the active type
Rotate cycles = { .rotations = 0.4 }; // int

You'll find that thinking of unions as a variant of its active state allows us to use unions as how would probably expect type unions to be used.

/**
 * Animate a rotation on an `object`.
 *
 * If `rotation` is a float, rotate by that angle in degrees.
 * If it is an integer, do that number of full rotations. (Negative for clockwise)
 */
void object_rotate(Object *obj, Rotate rotation);

Now the issue becomes: how do we know what an instance of a union's active type is? And the answer is consistent with the mindset that you should have if you've decided to use the language- you implement it yourself!

But if you've tinkered around with C before, you should notice that this is a very familiar pattern.

/**
 * Return the sum of n-length list.
 */
int sum(int nums[], unsigned int n);

nums loses the size information when passed as an argument, which means that we have to pass in the size as a separate argument.
The workaround to this is coupling the size information with the array, using a struct.

typedef struct {
  int* items;
  unsigned int size;
} IntArray;

/**
 * Return the sum of a list.
 */
int sum(IntArray nums);

We can couple the union type in a struct with an attribute that tells us what the union's active type is. Moreover, since we only really need some representation to check what a union's active type is, we can use an enumerated type (enum) for this, increasing its readability and makes the compiler check whether switch cases on that type are exhaustive when you turn on warnings.

So we observe that the main type constructs of the language interact harmoniously to create a feature than you probably might be taking for granted in higher level languages, type polymorphism.

Or the ability to do separate code branches depending on the type of a variable, without having to resort to hacks such as void pointers.

enum RotateType {
  FULL,
  ANGLE,
};

union _Rotate {
  int rotations;
  float angle;
};

typedef struct {
  enum RotateType type;
  union _Rotate unwrap;
} Rotate;

In fact, this type of structure has a name, a tagged union. The tag here is our extra attribute on our wrapper that determines the union's active type.

Tagged unions can be seen in various modern languages, most prominently in Rust (where they are referred to as Enums), Zig, and languages that heavily emphasize pattern matching.

Applications of tagged unions include but are not limited to:

the Result<T,E> type, which in of itself enables the concept of passing "errors as values," which is behavior that is way easier to deal with than throwing exceptions from anywhere
the Option<T> type, which allows encapsulation of null values.
- Interestingly enough, we don't actually need a union for this type, but the pattern of having a tag dictate the active type makes it still fall into this category.
Lexical tokens Token, for writing leaner parsers that allow for compiletime type checks on your Token variants.
and other use cases that require alternation over types. Think of tagged unions as being able to "boolean or" together types, while structs let you "boolean and" them.

More on C's tagged unions

But in C, using the type we've declared is not ergonomic at all.

// A Rotate ANGLE variant with value 90.0 degrees
Rotate right_angle = { .type = ANGLE, .unwrap = (union _Rotate) { .angle = 90.0f }};
// A Rotate FULL variant with value 2 rotations
Rotate doubleturn = { .type = FULL, .unwrap = (union _Rotate) { .rotations = 2 }};

The answer? Function macros, or as I like to call them, wizardry.

Macros should never be your first solution when it comes to problems you encounter in your code. You should only ever consider it when you need actual code to be written for convenience sake.

One way we could tackle this ergonomic issue is by storing the variant type out-of-band.

Instead of declaring it as a value, we encode that idea in the macro's name itself.

#define Rotate_FULL(_degrees) \
  ((Rotate) { .type = FULL, .unwrap = (union _Rotate) { .rotations = (_degrees) }})

#define Rotate_ANGLE(_angle) ((Rotate) { \
  .type = ANGLE,                         \
  .unwrap = (union _Rotate) {            \
    .angle = (_angle)                    \
  }                                      \
})

So now all we have to do to create instances of these unions are:

Rotate right_angle = Rotate_ANGLE(90.0f);
Rotate doubleturn = Rotate_FULL(2);

Or a much more explicit alternative, is to make your macro take in the variant and an anonymous union that corresponds to the type specified by the variant.

#define Rotate(_variant, _union) \
  ((Rotate) { .type = _variant, .unwrap = (union _Rotate) _union })

Rotate halfturn = Rotate(ANGLE, { .rotations = 180.0f });

This version is more applicable if your tagged union has more variants than macros you are willing to write, at the cost of being more verbose in creating instances. (Do note that there is no compatibility checking done with the value and the variant!)

Here's how you would go about accessing those fields.

union _Rotate unwrapped = doubleturn.unwrap;
switch (doubleturn.type) {
  case FULL:
    printf("Rotate 360deg %d times.", unwrapped.rotations);
    break;
  case ANGLE:
    printf("Rotate %.2fdeg.", unwrapped.unwrap.angle);
}

Rotate rotations[] = {
  Rotate_FULL(4),
  Rotate_ANGLE(45.0f),
  Rotate_FULL(0)
};

And for a much more interesting example, macros also let you (sort of) work with generics, by utilizing its preprocessed text concatenation using double hashtags ##.

Here's an implementation of the generic Result<T,E> type as found in languages like Rust.

enum ResultVariant { RESULT_OK, RESULT_ERR };

// the Error type to be used for all Results.
struct Error {
  unsigned int code;
  const char* message;
};

// a macro for creating a Result implementation for some arbitrary type T =====
#define deriveResult(T)         \
  union _Result_##T {           \
    struct Error err;           \
    int ok;                     \
  };                            \
  struct Result_##T {           \
    enum ResultVariant type;    \
    union _Result_##T unwrap;   \
  };

// shorthands for result instances, takes in the type of the Ok variant.  =====
#define Result_Err(ok_type, _code, _message) \
  ((struct Result_##ok_type) {               \
    .type = RESULT_ERR,                      \
    .unwrap = (union _Result_##ok_type) {    \
      .err = {                               \
        .code = (_code),                     \
        .message = (_message),               \
      }                                      \
    }                                        \
  })

#define Result_Ok(ok_type, _value)           \
  ((struct Result_##ok_type) {               \
    .type = RESULT_OK,                       \
    .unwrap = (union _Result_##ok_type) {    \
      .ok = (_value)                         \
    }                                        \
  })
// ============================================================================

// create Result_int
deriveResult(int);

// errors on negative params
struct Result_int area_rectangle(int l, int w) {
  if (l < 0 || w < 0) {
    return Result_Err(int, 1, "invalid dimensions");
  }

  return Result_Ok(int, l * w);
}

int main(void) {
  int l, w;
  char buffer[BUFSIZ];

  printf("input length and width:\n");
  fgets(buffer, BUFSIZ, stdin);
  sscanf(buffer, "%d %d", &l, &w);

  struct Result_int area = area_rectangle(l,w);

  // match on the Result variant
  union _Result_int unwrapped = area.unwrap;
  switch (area.type) {
    case RESULT_ERR:
      printf("ERROR: %s (Code %u)\n", unwrapped.err.message, unwrapped.err.code);
      return area.unwrap.err.code;
    case RESULT_OK:
      printf("The area is: %d\n", unwrapped.ok);
  }

  return 0;
}

`goto`

Though I won't be covering goto as in depth in this article (as they already do pretty much what you expect them to do, and in a manner that you also expect to do it with), know that I do share this same sentiment with it.

Edsger Dijkstra, a person who you should probably already know 1-2 years in any computer science related degree, has an article talking about when goto statement is considered harmful, entitled "Goto statement is considered harmful." And the main point he was getting at in said paper is the importance of being able to reason about your program as it grows dynamically in complexity, by knowing the sequence of instructions to get back to some point of a process after being stopped by some arbitrary action?

Or to put simply, how do you get back to a point in your program by tracing the code sequentially?

Now I believe that his article, along with this idea of goto being harmful has been terribly lifted out of context and echoed throughout the pedagogy of programming. That is "do not use goto, ever".

We should, as critical thinkers, be able to discern when ideas and principles are true, especially after factoring in context. goto, and any language feature for that matter, when thought of in a vacuum, should neither be good or bad. goto becomes bad when it obscures our ability to reason about the dynamic nature of our program, and good when it improves it.

In fact, it is so useful for handling exit cases of functions that with one quick lookup, you can see that goto is found all over the Linux kernel. Point is, if goto doesn't hinder your ability to trace your program, even if there's a more idiomatic way of achieving your desired behavior, it is not a bad use of it.

static int __init button_init(void)
{
        int error;

        if (request_irq(BUTTON_IRQ, button_interrupt, 0, "button", NULL)) {
                printk(KERN_ERR "button.c: Can't allocate irq %d\n", button_irq);
                return -EBUSY;
        }

        button_dev = input_allocate_device();
        if (!button_dev) {
                printk(KERN_ERR "button.c: Not enough memory\n");
                error = -ENOMEM;
                goto err_free_irq;
        }

        button_dev->evbit[0] = BIT_MASK(EV_KEY);
        button_dev->keybit[BIT_WORD(BTN_0)] = BIT_MASK(BTN_0);

        error = input_register_device(button_dev);
        if (error) {
                printk(KERN_ERR "button.c: Failed to register device\n");
                goto err_free_dev;
        }

        return 0;

err_free_dev:
        input_free_device(button_dev);
err_free_irq:
        free_irq(BUTTON_IRQ, button_interrupt);
        return error;
}

Conclusion

If C were to have any warts as a language, I do not believe it is with union or goto. I do not think it's perfect, especially when it comes to a lack of namespaces, the lack of a dedicated build system, and a substandard standard library (i.e. gets), but none of these flaws stop it from being an incredibly versatile language and one that makes you feel like a real programmer after writing a functioning program in it.

In fact, union and goto being as open-ended as they are provide the biggest opportunity for clever programmers to create ingenious solutions to their problems, and if you've programmed even the littlest bit, you'd know that's the most fun part of all of it.

Enjoy programming.

Figma for Programmers

tyrael — Tue, 07 Jan 2025 12:53:22 +0000

This article assumes you have fundamental knowledge of HTML/CSS, and won't cover prototyping and design systems. Moreover, this is not a tutorial, but a brief overview of notable features within Figma.

It is very likely that a major roadblock you will encounter as programmer who does side-projects is tackling with how the the user interface should look like. This roadblock won't really go away unless you end up with a UI/UX designer on your team, if you even have a team in the first place.

And in contrast to other problems, you should immediately know how to resolve this; that being a mockup. However, this doesn't exactly get rid of the problem but actually introduces another problem into the process. You now have to learn how to make mockups, and make them effectively, and most importantly, translatable into code.

I had to deal with this when I decided to try and create my own custom desktop interface from scratch using the Astal library, recognizing that in order to make the process productive and bearable, I had to grit my teeth and delve into UI/UX design, being primarily a programmer.

The time had come, I had to learn Figma. And these are the major takeaways I have from that experience.

Before I go into it, I would like to thank Sharmaigne Mabano and Kaye Jose for guiding me through the initial steps to properly setup a Figma mockup.

Preparing your palette, literally

Like every hobby programmer, I once tried my hand at game development which also led me down the path of pixel art. And a good habit I picked up from that is by preparing swatches of colors at a corner of my canvas that I will use for the drawing I was going to make. Not only did this give the art more direction but also a bit more organization that is just pleasing to my OCD.

This is also a good idea to do in Figma as not only can you visually see the colors beside eachother, but you can also set Library variables for your current project, letting you refer to the colors via their names instead of their hardcoded hex codes.

NOTE: Programmers love making variables for repeating things!

A good way of deciding colors for your palette is by getting existing ones online (a site I used a lot back when I was doing pixel art was Lospec), using Realtime Colors, or as a last resort, making your own using Color Theory. Of course I won't be able to tackle color theory in an article about Figma but do check out hue shifting for creating more vibrant shades of colors.

KEY FEATURE: Library variables

On `div`s and `flexbox`es

In making an effective design, it is not only important for it to be visually pleasing, but also feasible for translation into code. I like to think this is where the programmer perspective really comes into play, by already thinking of the code while designing, you are ensuring a smooth transition into that medium.

That is, to equate Figma frames as divs. This doesn't mean to just imagine them as such, but to quite literally use them everywhere you would see yourself using a div in. This includes grouping anad nesting other divs together, and creating separate backgrounds for sections.

For example: when creating a mockup for a navbar, it is common to have a split design, to have a logo on the left and the menus on right. In this example, I am designing my taskbar which has workspaces on the left and laptop battery power on the right.

We could do this by absolutely positioning everything and just figuring it out when coding, or:

The divs are highlighted here for demonstration purposes

We could setup the mockup in a way that the divisions are already declared. Not only does this make the design process easier, but also makes the coding require less overhead from laying out the divs in a way that resembles the design.

Another reason to do this, and probably one of the best features of Figma, is that we can set our frames into auto-layout mode. This initially feels confusing to look at, but my god does it save so much time.

A good parallel to auto-layout is the flexbox property of divs, wherein the arrangement of content can be declared with properties, including padding, spacing, and alignment. If you only get to take away one thing from this article I hope it is this one. I cannot emphasize how much easier designing gets when you start using this feature, especially since it can just get translated into display: flexbox in CSS, or flex in Tailwind.

Auto-layout will allow you to create scaleable and responsive designs fast, and translate them into code even faster. If you start desigining with the idea of divs and flexbox in mind, you are setting yourself up for success.

KEY FEATURES: Auto-layout and frames

Components and variants

If you have used any web development framework in the past decade or so, you have probably encountered the idea of component-based interfaces. We can use this mindset in Figma as well as they provide the option to create components from frames. These components act like the ones you know from web frameworks, letting you make instances from the parent component by using copy-paste, and edit properties from instances independent from the parent and other related components.

Like palette swatches, I create a separate frame just to hold all of my parent components, for easy reference and editing.

Moreover, components can be setup to have variants, that being the same component technically speaking, but with specific properties differing, which can be used to trigger appearance changes.

An example of this would be hover=true and hover=false variants. This naming is convention in Figma, denoting the properties that dictate that variant's appearance.

Setting up the variants allow you to make an instance of the parent component and simply assign the property in the instance, with a checkbox for boolean attributes, and a textfield for anything else.

And to implement variants in your code is a matter of creating CSS classes for them, or by using variants in component libraries such as shadcn.

KEY FEATURES: Components and variants

Conclusion

Don't be scared to try out Figma (like I initially was)! I can attest to it being a pleasure to work with. Making mockups is definitely an underrated skill for programmers, often times increasing a team's size solely to add a designer for that purpose.

But I would be lying if I don't mention how immensely gratifying it is to create a mockup from your vision as fast as you can in Figma, and then code with a well-engineered design as reference.

Conclusion: Learn Figma, even as a programmer not looking for a UI/UX career.

Rust-like Iteration in Lua

tyrael — Mon, 06 Jan 2025 13:22:38 +0000

This reading was inspired by Neovim's api Iter namespace. Be sure to check that out!

It is no secret that I adore functional patterns in programming. So any excuse I can get to use them is more than welcome in my code.

One of these patterns involve using functions to abstract transformations over lists, which we can do in a language like Python as:

a = [1,2,3]

map(lambda b: b + 1, a)
# or [ b + 1 for b in a ]

And in Lua as so:

function map(tbl, fn)
    local ret = {}
    for i, v in ipairs(tbl) do
        ret[i] = fn(v)
    end

    return ret
end

local a = { 1, 2, 3 }
map(a, function(b)
    return b + 1
end)

But this way of transforming, that being passing the iterable to be transformed as an argument, is quite cumbersome. Especially when it comes to composing or chaining these transformations together.

a = [1, 2, 3]
reduce(lambda ac, x: ac * x, filter(lambda c: c > 2, map(lambda b: b + 1, a)))

Elixir does a great job of eliminating this redundancy, by making it convention to have the iterable as the first argument, being able to leverage syntax sugar, implicitly passing the iterable as the first argument of the consecutive transformations.

a = [1, 2, 3]

a
|> Enum.map(fn b -> b + 1 end)
|> Enum.filter(fn c -> c > 2 end)
|> Enum.reduce(fn x, ac -> x * ac end)

Leveraging state

But using syntax sugar isn't the only way we can achieve this way of chaining transformations without deeply nesting our parameters. In Elixir, they have to do that because of state being immutable, but we aren't working within the confines of a strictly functional language when we are talking about Lua.

Let's take a look at how Rust tackles this problem.

let a: Vec<i32> = vec![1,2,3];

a.iter()
 .map(|b| b + 1);
 .filter(|&&c| c > 2);
 .fold(1, |ac, x| ac * x);

I use fold here with an initial value as to avoid doing an .unwrap() at the end.

Elegant chaining is achieved without the use of syntax sugar! And if we really read into it, we are first wrapping it into the std::iter class (trait to be more technically correct), which has self-returning methods!

So to achieve this in Lua, all we have to do is figure out how to wrap new methods ontop of our existing array so we can chain the transformations.

Metatables

Lua does not have "classes" in the strict sense, but we can implement them using metatables. In fact, we can straight up just ignore the idea of a class and tackle this problem as a matter of implementing interface methods for our array.

First, we define a table that's going to contain all of the implementations we want to apply to our array, and a constructor function that sets that table as our indexing table.

local Iter = {}

function iter(tbl)
    -- do note that this will replace any existing metatables on tbl
    setmetatable(tbl, { __index = function(self, key)
        return Iter[key]
    end})
    return tbl
end

What's happening here is we are telling our tbl array that whenever we cannot find a specific key in our array (which we won't, assuming the table is just used as an array and not a hashmap), to call the __index function instead of just returning nil.

This __index function is what we call a metamethod, functions that get called implicitly by Lua under specific conditions. In the definition we are saying to look for the key in the Iter table whenever it doesn't exist in the current table. Moreover, Lua actually provides a shorthand for this.

function iter(tbl)
    setmetatable(tbl, { __index = Iter })
    return tbl
end

So clean! However, there is an issue here, that being we are mutating our state directly. Transformations are usually done on copies of arrays as to maintain immutability, so let's do that here.

function iter(tbl)
    local cpy = {} 

    for i, v in ipairs(tbl) do
        cpy[i] = v
    end

    setmetatable(cpy, { __index = Iter })
    return cpy
end

Do note that this method of copying will still use references when copying over nested tables, so be careful about that!

Now we can do our magic.

Implementations

We'll define the implementations on our Iter table.

function Iter.map(self, fn)
    for i, v in ipairs(self) do
        self[i] = fn(v)
    end

    return self
end

This works, but it doesn't exactly solve our initial issue of passing in the iterable as an argument. Here we can leverage syntax sugar, ontop of our leveraging state, to get there!

Lua provides syntax for : calls, which can be used in definitions to declare an implicit self argument as the first parameter of the function, and in calling to use the left-hand side of the : as the self argument. Here it is in action.

function Iter:map(fn)
    for i, v in ipairs(self) do
        self[i] = fn(v)
    end

    return self
end

local arr = iter({1,2,3})

arr:map(function(a) return a+1 end)
   :map(function(b) return b*2 end)

And this works, and looks very cool (which should ultimately be the standard for all of your code). All that's left now is to implement the rest of the transformation functions you need (a little brain exercise for the reader) and you're set.

Lua as your favorite Programming Language

tyrael — Sun, 05 Jan 2025 10:05:04 +0000

I personally see myself as a generalist when it comes to programming, growing up on videos by engineers such as Michael Reeves and William Osman, I tend to code things I want to make.

And of course that entails looking for a medium to code as much things as I can with the highest amount of enjoyment that can be derived from it. Categories in which I believe Lua is a perfect fit in.

Lua is a performant, general-purpose language, the likes of Python and Ruby. But why choose it over the alternatives?

Simplicity

Hot take, but I really enjoyed the feeling of writing in C. There is a much heavier sense of accomplishment to hacking together something that works in C than in a higher level language such as Python as it feels like you can say that you made it brick-by-brick, with as little dependencies as possible.

Now it would be arguable to contest that Lua can be strictly faster than Python as modern-day technologies allow both interpreted languages to use just-in-time compilers (code compilation during runtime) which then set the precedent for the speed, not the language. But it is straight up factual to state that Lua is simpler than Python and C, boasting only 22 keywords (C has 32!) and a syntax that feels very uncompromising.

A design choice of Lua that took a while to grow on me was the use of do ... end syntax to denote blocks, but I found myself preferring it over Python's reliance entirely on indentation. This does not stem from enforcing indentation in the syntax itself, but the connectedness I feel from explicitly enclosing related code in blocks. Moreover, when you get used to this syntax and encounter a line such as if a > 5 then print(a) end, it immediately makes sense what happens, even when you haven't encountered it in one-line form previously.

Lua actually has a built-in character-based string patterns for matching, opting to use that instead of adding built-in regex support as regex in of itself would be bigger than the language itself. This conscious design choice is incredibly admirable, attesting to its dedication to simplicity.

There is definitely merit to making complexity (your code) emerge from simplicity (your building blocks).

Tables

When you ask someone about this language, it would be very unlikely for them to not bring up tables as the only data structure in Lua. And to me, I think the existence of tables in of itself doubles down on this idea of complexity emerging from simplicity, in how you can implement pretty much anything you will ever need with tables, despite it not being obvious at first glance.

Arrays? Tables. Hashmaps? Tables. Bags? Tables. Linked lists and graphs? Tables!

Moreover, tables even allow you to define OOP-style constructs just by letting you interface with a little bit of metaprogramming. Syntax sugar even exists for self-referencing methods (for any defined function key you can pass in a self parameter by using : for access instead of .)!

Oh, and it's not really that much of a big deal to adjust to 1-indexing.

Homebrewing

Lua being simple forces you to implement your own libraries for your usecases. I believe this is where a lot of the charm of the language comes from, a design principle undoubtedly inherited from C.

Not only does this ensure your program is as compact as it can be, it also helps you be much more intimate with the code you are writing.

Setting up your codebase with libraries specifically catered for you and your team, and seeing it all come together is incredibly gratifying as Lua provides an easy to use interface for importing user-defined modules.

Not only that, but with Lua LSP type annotations you can also guarantee that your documentation pretty much writes itself, which is a big win for developer experience.

Usecases

Lua is as general purpose as it can get, ranging from creating games in Roblox and the love2d framework, modding APIs for various games such as Hades 2 and Binding of Isaac: Rebirth, to being used as configuration languages for Wezterm and Neovim (the best IDE), and defining desktop widgets via Aylur's GTK Shell, and even writing embedded C!

All of that while being a pretty solid scripting language (I did some problems of Advent of Code 2024 in Lua!).

It is very hard to miss Lua whenever you immerse yourself in programming as it lends itself as not only a language, but a powerful framework for creating interfaces.

The sheer applicability of Lua allows you to rapidly improve as a software developer as you can practice workflows in your controlled environment and release cycles. I cannot stress how important it is to start learn programming with a fast feedback loop as a lot of the concepts and theories can easily be missed with the lack of visualization.

Conclusion

I have programmed in a lot of languages in search of one that matches my philosophy and preferences, and I have found all of that in Lua. I encourage you to try it with its many usecases as you might discover that its your favorite language too.

Understanding Python Iterables: Generators

tyrael — Sat, 31 Aug 2024 07:03:32 +0000

Header by: Santiago Uribe Uribe Domínguez
Edited by: Sharmaigne Mabano

It is inarguable that one of Python's strongest suits is how it deals with iterables, or traversable objects.

When you're new to Python, something that immediately sticks out is the syntax of the for loop.

# prints 0 to 9
for i in range(10):
    print(i)

You'll find that Python strictly enforces the foreach control structure that can be found in other languages, and if you're used to the C-like way of writing for-loops, this might have, pun intended, thrown you into a loop.

But in understanding this fundamental concept in Python, we actually allow ourselves to write more elegant and terser code. So let's incrementally tackle this topic.

Iterators

We'll start by defining iterators as objects we can traverse through one item at a time. Think anything you can pass into a for loop, and iterables as objects that can be turned into iterators.

Note that this traversal cannot go backwards.

Furthermore, we can actually create our own iterable classes.

class Fibonacci:
    def __iter__(self):
        self.a = 0
        self.b = 1
        return self

    def __next__(self):
        temp = self.a
        self.a = self.b
        self.b = temp + self.a

        return temp

for n in Fibonacci():
    print(n)

All that we have to define are the __iter__ and __next__ methods!

__iter__ returns the object to be used for iteration (this is what turns our iterable into an iterator) whenever our object is invoked in the context of an iterator (in this case it is invoked as the iterable for a for loop). In this example, we use it as an initialization function of sorts, but you can just think of it as the constructor for your iterator instance.

If that had too much jargon, all that you need to know is that what __iter__ returns is the object to be used in iteration!

__next__ is the function that gets called on every iteration, its return being the value for that current loop.

Side note: dunder (double underscore) methods are just special methods for objects that you can call by passing the object in the dunder method's base name (without the underscores), or by invoking the dunder method on the object as an attribute.

An example of this is:

a = Fibonacci() # we create our iterable object (this isn't an iterator yet)

# Let's try calling the __next__ dunder method
next(a) # AttributeError: 'Fibonacci' object has no attribute 'b' (because iter hasn't been called)

b = iter(a) # We bring our object into an iterator context (this is done implicitly in for loops)

# both ways of calling the dunder method works
next(b) # 1
b.__next__() # 1

next(b) # 2
next(b) # 3
next(b) # 5

For the keen-eyed, you might have noticed that even though we're allowed to traverse this iterable using __next__ or a for loop, you can actually keep getting the next value infinitely!

If this infinite looping behavior is not your intention, you can simply add a base case to your __next__ method, by raising a StopIteration exception.

def __next__(self):
    # stop the looping 
    if self.a > 100:
        raise StopIteration

    temp = self.a
    self.a = self.b
    self.b = temp + self.a

    return temp

This allows your for loops to stop iterating on your set condition. However if you try to call __next__ on an iterator that has hit StopIteration, it will throw a runtime error.

In fact, we can see these dunder methods __iter__ and __next__ on any iterable object in Python such as lists and tuples! We can use the __dir__ dunder method to check for all of the methods found in an object.

a = [1,2] # a list, a common iterable

print('__iter__' in dir(a)) # True
print('__next__' in dir(a)) # False

That's odd, the list object has an __iter__ method, but no __next__! Why is that?

Generators

Generators are special kinds of functions that instead of returning a single value, returns an iterator object. But instead of using the return keyword, it implicitly returns the iterator object using yield. Let's see this in action by re-implementing our Fibonacci iterator.

def Fibonacci():
    a = 0
    b = 1

    while a < 100:
        temp = a
        a = b
        b = temp + a

        yield a


a = Fibonacci() # our iterator object

print(next(a)) # 1

for num in a:
    print(num)  # 2 .. 144

We get our iterator object on the initial call of our function a = Fibonacci(). This is evident by our ability to call __next__ and use it as an iterable in a for loop. However, we can clearly see that there is no explicit definition for the __next__ method, which means that it is baked into the logic of the definition itself.

Now what does this mean? Lets try to follow the execution of our iterator on the first 3 __next__ calls (or for loop iterations):

--- first __next__ ---

a is defined
b is defined

we enter the while loop
we move forward with the fibonacci pattern
we return a

--- second __next__ ---

we enter the while loop
we move forward with the fibonacci pattern
we return a

--- third __next__ ---

we enter the while loop
we move forward with the fibonacci pattern
we return a ...

We can see here that for every __next__ call, we can think of our iterator running through our defined function up until it hits a yield, where it uses that value to return for that specific iteration. Moreover, for the next iterations, we simply pick up from the line after the yield where we left off.

This means that instead of having to raise StopIteration by ourselves, we can simply just let the function exit, greatly simplifying our conditions.

Note that this also means return in generators become analogous to raise StopIteration (and are only provided values in advanced cases we won't cover here)!

So really, we aren't learning anything new here in the context of iterators, but a terser syntax and a more accessible interface for creating iterators!

Let's go back to our cliffhanger from the last section, by taking a look at the __dir__ of a generator.

def a():        # a function becomes a generator in the presence of a `yield` keyword
    yield 3

x = a()         # we create our generator object

print('__iter__' in dir(x)) # True
print('__next__' in dir(x)) # True

Since generators do have instances of the __iter__ and __next__ method, we can confirm that it is in fact an iterator. And how is this relevant?

Recall that:

Any function becomes a generator when it has a yield inside of it.
Generators are simply functions that return an iterator object, with it's __next__ function as its definition (kind of)
__iter__ method is used to implicitly return the object used for iteration whenever the context calls for it
- These contexts include being casted into a iterator with iter, being used as an iterable for a for loop, and as we'll later learn: being unpacked.

We can deduce that, under the hood, native Python iterables define their __iter__ methods as generators, making the __next__ absent from the class definition, but not from its iterator instance.

a = [1,2]

print('__iter__' in dir(a)) # True
print('__next__' in dir(a)) # False

b = iter(a)                 # we bring it into the context of an iterator

print('__iter__' in dir(b)) # True
print('__next__' in dir(b)) # True

Note that this assumption is actually just an oversimplification! As lists and tuples actually return a special list_iterator and tuple_iterator object respectively, demonstrating that you don't necessarily have to return self in the __iter__ method.

Putting a generator in place of the __iter__ method is not only an elegant way of writing it, but it also serves a purpose for encapsulating the __next__ method inside of the iterator instance itself, since if you can remember-- we weren't even able to use __next__ until our object became an iterator anyway!

Laziness

Besides the fact that knowing how a language works is pretty cool, generators (and by extension, iterators) also serve as a massive point of optimization for most Python programs. Which we can just derive from its name, it generates values.

In fact, I would go as far as to say that coding in Python becomes infeasible without generators, all because of their lazy evaluation.

Lazy evaluation is not a new concept in Computer Science, in fact it's a byproduct of functional programming, wherein we may delay the execution of a transformation on data up until the point where we actually need it.

A good analogy of this is being given ingredients for a meal that you have to cook tonight. With all of those ingredients and your cooking gear and whatnot, you can argue that you technically already have the meal, you are simply not making it until tonight. This could be for various reasons, one of which could be that it is easier to store the ingredients than the entire meal itself.

When we created the Fibonacci generator, we could argue that we did have the Fibonacci numbers up to 144, we just simply weren't calculating them until we had to. This approach saves resources from our program as we don't end up keeping all of the memory we need up front, i.e. if we wanted to keep the Fibonacci numbers less than ten million, but we're still technically storing the numbers.

Think of our ubiquitous range function, an example of a generator, as we know that range doesn't keep a list in memory, but rather generates the numbers sequentially (we know this by the fact that we can only traverse the iterable in the direction indicated by the step parameter).

In fact, you should go ahead and try to implement some preexisting generators in your free time, to see how well you understand Python! Notable generators are enumerate, zip, map, filter. As for range, it actually requires a bit more prerequisite knowledge that you may originally expect, so we'll be covering it on a follow-up article.

Good luck!

Functional Patterns: The Monad

tyrael — Sat, 06 Jul 2024 13:46:27 +0000

This is the final part of a series of articles entitled Functional Patterns.

Make sure to check out the rest of the articles!

The Monoid

Compositions and Implicitness

Interfaces and Functors

Recursion and Reduces

Zips and the Applicative

What's the problem?

A monad is just a monoid in the category of endofunctors, what's the problem?

Is a quote from A Brief, Incomplete, and Mostly Wrong History of Programming Languages, when he mentioned Haskell.

Though memed throughout the times, this statement actually manages to hold some truth to it still, being a pretty good description on what monads are.

No pattern had fascinated me more than the Monad, and for a while I had obssessed over being able to understand it, only for it to slip out of my grasp every single time. Monads had been so notable to me as there's a long running joke that monads are a mystery— because when you learn it, you forget all ability to teach and describe it.

For a while I had been reading about this pattern that kept getting praised in the functional programming community, but I hadn't come across a definition— an explanation, that did it for me.

But somewhere along that road, after all those times sunk into understanding this pattern— I felt like I could comfortably say that I had reached an understanding on it. It stopped being an "Aha! I think I got it!"

And that really was the motivation behind this article series, to help curious individuals tackling this niche I had delved into a year prior, have a better time than I did. I told myself:

Six articles, building up to a decent explanation on the Monad.

And here we are. I hope I hadn't lost you on the way here, but we've made it. What's left now is tackling the main pattern itself.

In the Category of Endofunctors

Let's slowly take apart the quote describing monads.

... in the category of endofunctors.

These are terms we had already encountered, and what this is telling us is that the Monad deals with endofunctors, not any normal value we're used to. Let's take a look at its Haskell definition.

class Applicative m => Monad m where
    (>>=) :: m a -> (a -> m b) -> m b
    return :: a -> m a
-- ...

There it is! We see that to be a Monad, you first must be under the Applicative typeclass (which are endofunctors that can be applied using <*>), which further requires you be under the Functor type class in the first place (you can map endofunctors using fmap).

So, like the article on Functor and Applicative, we are going to be talking about functions applying onto some data type, some struct, we have defined. Notably using this >>= operator here, also referred to as bind.

We also have this function return, which should already be pretty familiar to us.

class Functor f => Applicative f where
    pure :: a -> f a
    -- ..

class Applicative m => Monad m where
    return :: a -> m a
    -- ..

It's essentially an alias for our pure function previously defined in Applicative! Surely there has to be a reason why it's called return now? We'll discover that shortly.

A Monoid

Recall our definition of a Monoid.

A type is said to be a Monoid over some binary function or operation if the result remains within the domain of the type, AND there exists an identity element.

That can only mean one thing, a Monad is just defining some binary operation over endofunctors! This is the next piece of our puzzle, let's take a look at the definition of bind specifically:

If you're a bit confused, remember that a Monoid is merely an interface that requires you have an operation that takes two arguments of the same type, and produce the same type. This is why we can say + is a Monoid over Int, and also Int is a monoid over +.

class Applicative m => Monad m where
    (>>=) :: m a -> (a -> m b) -> m b
    -- ..

We see that bind is not only a binary function, but also that it returns a data type m b, which corresponds to the same category as our input m a, despite them having differing internal types— this has to be our Monoid operation! Let's compare it with the other operations defined in the previous type classes leading up to it, renaming all type constructors as f, for clarity.

(<$>) :: (a -> b) -> f a -> f b     -- fmap
(<*>) :: f (a -> b) -> f a -> f b   -- apply
(>>=) :: f a -> (a -> f b) -> f b   -- bind

Let's add a few spaces to highlight the pattern and swap out >>= with =<<, its flipped equivalent (arguments are swapped places).

(<$>) ::   (a ->   b) -> f a -> f b
(<*>) :: f (a ->   b) -> f a -> f b
(=<<) ::   (a -> f b) -> f a -> f b

So we see that they all in fact deal with some functor, but in slightly different ways.

fmap takes a function and then a wrapped value, mapping the function over the wrapped value.
<*> takes a wrapped function and a wrapped value, applying the wrapped function over the wrapped value.
>>= takes a wrapped value, a function that returns a wrapped value, and then returns that wrapped value.

Moreover, because it is a monoid over endofunctors, this means:

We can chain these together associatively
Our final return type is an endofunctor in the same category
- which in turn means, our final type stays in the same category.

Monads in Practice

Lets say we have an arbitrary cipher, wherein characters in the alphabet are converted to any other arbitrary character in the alphabet. We keep this cipher as a dictionary (also known as a hashmap) that takes an encoded Char and returns the decoded Char.

import qualified Data.Map as M

cipher :: M.Map Char Char
cipher = undefined -- definition omitted

Now we create a decode function, remember that this operation might fail (when the key doesn't exist), so we have to use the Maybe data type.

decodeChar :: Char -> Maybe Char
decodeChar = (`M.lookup` cipher)    -- wrapping in backticks turn a function into infix form
                                    -- so we're partially applying the second argument

-- equivalent to:
-- decodeChar = flip M.lookup cipher   -- C-combinator, flips the arguments

M.lookup is a function that, well, does a lookup on a M.Map, with your given key (in this case our encoded Char), and returns a Maybe Char, because the key might not exist in the M.Map in which case it will return a Nothing.

Now say we want to then lowercase the resulting characters of our decoding. We would have to compose toLower function to our call, but there's one issue!

toLower :: Char -> Char

toLower doesn't take a Maybe Char! If we recall the available functor composers we have, this is actually no problem as this is just an fmap.

decodeChar = fmap toLower . (`M.lookup` cipher)

-- or even ...

-- we wrap the function in Maybe, then apply using `<*>`
decodeChar = (pure toLower <*>) . (`M.lookup` cipher)

Now say we want to convert our lowercased character into its ASCII value, we would have to do another composition on fmap.

decodeChar :: Char -> Maybe Int
decodeChar = fmap ord . fmap toLower . (`M.lookup` cipher)

And we can continue this for god knows how long, but the issue is starting to rear its head. This type of composition is kind of annoying to write! Let's try to write it using Maybe's Monad bind.

decodeChar :: Char -> Maybe Int
decodeChar c =
  M.lookup c cipher
    >>= return . toLower
    >>= return . ord

This works! And is so much cleaner. We can see return make its appearance here, and the reason it's called return, is not because it returns value in the imperative sense, but because it's usually the last call you make inside a function required by bind, because you have to return to your Monad type!

Let's think about that even deeper and realize that the reason we have to return to our Monad is because: while we're inside the function required by our bind, we implicitly "unwrap" our value, so we can do our own logic on it, before rewrapping it at the end, so we can now completely abstract "unwrapping"!

Note the double-quotes on unwrapping, it's because we aren't actually unwrapping the value, as that might cause a runtime error depending on your data type's logic (unwrapping a Nothing causes an error).

decodeChar :: Char -> Maybe Int
decodeChar c =
  M.lookup c cipher
    >>= return . ord . toLower

So now we can do our usual compositions, inside our Monad type! Moreover, Haskell has an even more legible syntax for this, the do.

decodeChar :: Char -> Maybe Int
decodeChar c = do
  decoded <- M.lookup c cipher -- Make value inside Maybe accessible

  return . ord . toLower $ decoded

And in this form, the return being at the end of the call even resembles an imperative language!

Note that because we've done our functions without unwrapping, we never risk unwrapping into a runtime error! Moreover, when you implement a Monad, it's up to you how you want to do their compositions, as long as you follow the 3 axioms of left-identity, right-identity, and associativity!

These axioms won't be covered here, but they shouldn't get in your way that often (and you'll rarely need to implement a monad in the first place)

concat . map (replicate 2) $ [1, 2, 3]  -- [ 1, 1, 2, 2, 3, 3 ]
concatMap (replicate 2) $ [1,2,3]

-- `bind` for the List monad is equivalent to `concatMap`!

[1,2,3] >>= replicate 2

Imperatively speaking,

But how is the concept of the Monad relevant to languages outside of Haskell and other functional languages? Is it relevant?

First of all, it's not all about you, imperative programmer! Second, leveraging the concept of monads allow us to write succinct (well, after you write the code to force FP into your imperative program), and chainable code.

Behold, the Maybe monad in Python:

class Maybe:
    def __init__(self, value) -> None:
        self.value = value

    @staticmethod
    def just(value):
        return Maybe(value)

    @staticmethod
    def nothing():
        return Maybe(None)

    def __str__(self) -> str:
        match self.value:
            case None:
                return "Nothing"
            case x:
                return f"Just {x}"

    def __eq__(self, other) -> bool:
        return self.value == other.value

    def bind(self, *fns):

        for fn in fns:
            if self.value == None:
                return self.nothing()
            self.value = fn(self.value).value

        return self.just(self.value)


def search(n, lst) -> Maybe:
    for i, v in enumerate(lst):
        if v == n:
            return Maybe.just(i)
    return Maybe.nothing()

result = search(4, [3, 4, 2]).bind(lambda a: Maybe.just(a+5))
print(result) # Just 6

result = search(5, [3, 4, 2]).bind(lambda a: Maybe.just(a+5))
print(result) # Nothing

Incredible and outrageous. Just the perfect mix.

And that just about does it! I hope you enjoyed this entire series, it has been about a year in the making. I hope you learned something, and most importantly, enjoyed the time you invested! If you have any questions, feel free to contact me in my socials, or in the comments down below, I will try to make time.

What's the problem?

I'd like to thank Sharmaigne for proof-reading, Tsoding for being a very helpful resource, and myself for actually committing to this grind.

Functional Patterns: Zips and the Applicative

tyrael — Thu, 04 Jul 2024 11:41:58 +0000

This is part 5 of a series of articles entitled Functional Patterns.

Make sure to check out the rest of the articles!

The Monoid

Compositions and Implicitness

Interfaces and Functors

Recursion and Reduces

Functor Recap

Learning about Functors have taught us the very important function that is fmap, or mapping a function on a Functor interface (most commonly on the array).

Remember, the Functor interface differs from the actual term functor. Members of the interface Functor,
to put simply, can be mapped over by endofunctors (which are a type of a function that maps a category to
itself).

# python
map( lambda a: a**2, [1, 2, 3] )  # [1, 4, 9]

Mapping a function on an array is a pretty common operation, a transformation on your data, if you may. But what if we wanted to apply a different function to each element? In terms of using map (or fmap), we are out of luck, as the functor supported by map are applied to all of the elements.

Zips

Say we have an array of int, our points in a game show. We'll get this in array for every round of the game.

# points per round
 [4, 3, 8, 1]
# r1 r2 r3 r4

We'd like to get the total of our score. However, we are told that points are worth more in the later rounds! That is, every point is worth the round it was gained in.

Let's try to get these values programatically. Let's first take an imperative approach, by using the index of our current value + 1 to multiply at our current number. We'll do this in Go, for a clearer demonstration:

rounds := []int{ ... }
result := 0

for (i := 0; i < len(rounds); i++) {
   result += rounds[i] * (i+1)
}

return result

then in Python:

rounds = [ ... ]
result = 0

for round, score in enumerate(rounds):
    result += score * (round + 1)

return result

We achieve pretty similar code, except for how we're now using a function named enumerate. Now what exactly does enumerate do?

enumerate(["a", "b", "c", "d"]) # [ (0, "a"), (1, "b"), (2, "c"), (3, "d") ]

Ah, the enumerate function "maps" some function to our original array, turning it into an array of pairs containing the index and the original value. But this can't be any ordinary functor, since there can't be any function that can achieve this changing value without side-effects!

Let's try to work backwards, and separate the pairs into their own arrays.

a = [ 0,   1,   2,   3 ]
b = ["a", "b", "c", "d"]

It shouldn't be that hard to get back to our paired array.

a = [ 0,   1,   2,   3 ]
b = ["a", "b", "c", "d"]
result = []

for i in range(len(b)):
    c.append( (a[i], b[i]) )

return c

We can simplify this further by realizing our a array is actually just range(len(b)).

a = range(len(b))
b = ["a", "b", "c", "d"]
result = []

for i in a:
    result.append( (i, b[i]) ):

return result

# also can be written as
# [ (i, b[i]) for i in a ]

Now we've implemented a function that takes two arrays a and b, and pairs them up into a resulting array! This is called the zip function. And the enumerate function is just a specialization of this, a zip with the first argument as the range(len(b)) of the second argument.

This is a simplified implementation for Python, as zip and enumerate actually return generators, and
mostly likely don't need to use range as a dependency.

b = ["a", "b", "c", "d"]
[*zip(range(len(b))], b) == [*enumerate(b)]  # [ (0, "a"), (1, "b"), (2, "c"), (3, "d") ]

Also, we've unlocked a whole new world for our map function, since now we can do differing partial applications for every element!

-- haskell
zip [3 .. 5] [9 .. 11] == [ (3, 9), (4, 10), (5, 11) ]
-- moreover, since functions are values...
zip [1 .. 3] [(*4), (+5), negate] == [ (1, (*4)), (2, (+5)), (3, negate)]

And since now we're in the array category once again, we can simply map or reduce over these pairs to perform our transformation!

points = [4, 3, 8, 1]

-- we pattern match on the tuple to multiply both elements
sum . map (\(a,b) -> a * b) . zip [1..] $ points

-- alternatively we can use the `uncurry` function, which does that
sum . map (uncurry (*)) . zip [1..] $ points

-- uncurry and mapping a zip is such a common pattern that it can be written as `zipWith`
sum . zipWith (*) [1..] $ points

-- point-free definition
totalScore = sum . zipWith (*) [1..]

Applicatives

A much more specific interface that is relevant to us is the Applicative typeclass.

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
--  ...

What this means is that:

in order to be Applicative, you first must be an instance of Functor.
You have to define a function pure, which takes any type and then wraps it with your type constructor f (again, this is synonymous to a struct)
You have to define a function <*>, which applies a wrapped function f (a -> b) to your wrapped value f a resulting in a wrapped result f b.

The following are additional axioms that need to be fulfilled ontop of being a valid member of the Functor typeclass. You don't have to fully understand these right now, but I figured I shouldn't omit them.

pure id <*> v = v                            -- Identity
pure f <*> pure x = pure (f x)               -- Homomorphism
u <*> pure y = pure ($ y) <*> u              -- Interchange
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition

The identity axiom states that applying a wrapped id (identity function) does nothing, working like the unwrapped id function.
The homorphism axiom states that applying a wrapped function to a wrapped value is equal to applying the function to the value and then wrapping it.
The interchange axiom states that applying u to a wrapped value is equal to applying a wrapped partial application of $ (thrush) of the original value to the function.
- ($ a) f is the same as f $ a or f a.
The composition axiom states that applying a wrapped (.) (composition function, b-combinator) is equal to composing the applied function to the following applications.

If we look at the signatures of the two main functions here fmap and <*>:

fmap  ::   (a -> b) -> f a -> f b
(<*>) :: f (a -> b) -> f a -> f b

We see that the only difference between these two is that Applicative has your functor wrapped in the same category (or data type) as your inputs!

The Maybe Monad

A ubiquitous Monad (which requires it be an Applicative) is the Maybe monad. We won't be talking about its Monad aspects here but what it does, to put simply, is act as context for functions with optional returns.

data Maybe m = Just m | Nothing

What this says is: Maybe is a data type (can be thought of as a struct) that holds type m and can either be a Just m or Nothing. An example of a function using this data type is:

findIndex :: (a -> Bool) -> [a] -> Maybe Int

findIndex even [1, 3, 4, 5] == Just 2
findIndex even [1, 3, 5] == Nothing

What findIndex does is find the first index wherein a predicate returns True. Now of course, this has a case wherein the predicate never returns True, and what would we return in that case? This is where the Maybe monad comes in, by wrapping our result in the Maybe type, we can return a Nothing in this case, and when we do find a True case, we just have to wrap our return with Just.

And if we're certain that we will always return a Just, we can just unwrap it using the fromJust function.

Since Maybe is under the Monad interface, and therefore an Applicative and Functor, we can do the things we were able to do on Applicative and Functor on it.

-- Being a functor:
fmap (* 2) (Just 4) == Just 8   -- we can map on it because its a functor, removing the need to unwrap
fmap (* 2) Nothing  == Nothing  -- which allows us to safely do operations on it.

But what if we needed to perform operations on multiple instances of a Maybe? We would have to unwrap them both, and then apply the function, right? However, this poses as risk— as unwrapping a Nothing will cause a runtime error, and writing all of that is just, horrible.

import Data.Maybe

Just (fromJust (Just 4)) + (fromJust (Just 5))  -- Just 9
Just (fromJust Nothing + (fromJust (Just 5))    -- ERROR!

Applicative allows us to compose functions without unwrapping our data types using the <*> function! Recall that all it does is apply a wrapped function, so we simply need to get to that point first. This is made more terse by the infix version of our lovely fmap function, written as <$>.

-- `pure` typed in the context of `Maybe Int` wraps our value in Just.
(pure 5) :: Maybe Int == Just 5

-- Applying a wrapped function
Just negate <*> Just 5 == Just (-5)
Just (+5)   <*> Just 2 == Just 7

-- Applying Nothing on either side resolves to Nothing
Nothing     <*> Just 5 == Nothing
Just (+5)  <*> Nothing == Nothing

fmap (+2) (Just 3) == Just 5
(+2) <$> Just 3    == Just 5        -- infix

(+) <$> Just 5 == Just (+5)         -- we get a wrapped *partially applied* function!

-- Therefore ..

(+) <$> Just 4 <*> Just 5 == Just 9   -- Composition!
(+) <$> Just 4 <*> Nothing == Nothing -- Composition!

The Maybe is analogous to Rust's Option type (although they do not have a way of simply composing these types), in that it can be used to avoid using sentinel or null values in your code altogether! This can even be further extended to handle errors in your code as a Nothing always propagates throughout the composition.

The ZipList Applicative

From reading the documentation, we actually find out that [] is also a data type of the Monad interface, again making it an Applicative and a Functor. We won't be demonstrating it's Functor properties as we've already covered that in a previous part of the series.

-- `pure` in the context of `[Int]` creates a singleton list
(pure 5) :: [Int] == [5]

-- Applying a list of functions to a singleton list returns a list of the applications!
[negate] <*> [5] == [-5]
[(*3), abs, (+2)] <*> [5] == [15, 5, 7]

-- Applying to our empty list always returns an empty list
[] <*> [3, 4] == []
[(*3), abs, (+2)] <*> [] == []

-- Applying a list of functions to a list of elements, performs a cartesian product
[(+2), (*3)] <*> [5, 2, 1] == [7, 15, 4, 6, 3, 3]

What's interesting with the list of functions applied to a list of values is that: it performs the function on all combinations of the functions and elements. Moreover, they are kept in a flattened list. This would be equivalent to:

result = []

for x in values:
    for f in functions:
        result.append(f(x))

# or
[ f(x) for x in values for f in functions ]

All within a single line.

We can actually implement the zip behavior of lists using an Applicative interface!

Let us define a ZipList data type.

-- we define our struct that holds an array of `a`
data ZipList a = ZipList { getZipList :: [a] }

-- we define its membership to the Functor typeclass
instance Functor Ziplist where
    -- we say that mapping on a ZipList is just mapping over its embedded array
    fmap f (Ziplist a) = Ziplist (map f a)

instance Applicative ZipList where
    -- we say that applying a list of wrapped functions is just zipping over wrapped values
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

However, we lack one definition here: pure. I've intentionally skipped this because this is a good demonstration to show where the axioms come into play.

Say we define the following:

pure x = ZipList [x]   -- mirroring the definition for `pure` of [], we put x in a singleton list

Recall that according to the identity axiom:

pure id <*> v == v

This definition falls apart when we substitute v as the infinite list [1..]

pure id <*> v == v

ZipList [id] <*> [1..] == ZipList [1..]
ZipList (zipWith ($) id [1..]) == ZipList [1..] -- zipWith truncates based on the shorter list
Ziplist [1] != ZipList [1..]                    -- false!

The problem with zip is that it truncates based on the shorter list, meaning for an application to be valid, the list fs must be infinite! So the definition of pure follows from that.

instance Applicative ZipList where
    -- we say that applying a list of wrapped functions is just zipping over wrapped values
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

    -- We say that the `pure` of some element x, is the infinite list of itself
    pure x = ZipList (repeat x)

And if you think about it— applying an infinite list of id to a finite list of x, will always return you the original list! Cool!

It goes without saying; there are so many more applications for the Applicative pattern out there, I hope you find them and recognize them!

And that concludes the penultimate part of this series! I hope you're enjoying and are able to keep up, if not, feel free to contact me for clarifications. I hope you learned something new, and see you in the last part The Monad!

Reference: https://en.wikibooks.org/wiki/Haskell/Applicative_functors

Functional Patterns: Recursions and Reduces

tyrael — Wed, 03 Jul 2024 10:02:16 +0000

This is part 4 of a series of articles entitled Functional Patterns.

Make sure to check out the rest of the articles!

The Monoid

Compositions and Implicitness

Interfaces and Functors

State

A big part of what defines functional programming— is the immutability of state. Because via this, we can immediately guarantee idempotence, a strict mapping of our input to output, just like in Mathematics.

Idempotence or referential transparency is just a fancy way of saying: If you give me x, I will always give you y. Moreover, referential transparency specifically, says that you can replace all occurrences of your function with the actual function body and your code should be functionally the same.

# python
def double(n):
    return n * 2

double(n)

# should be replaceable by

n * 2

At first glance you might probably go: "Well, duh, a function call is pretty much substituting code."

But this is sometimes not true, specifically when your function has side-effects.

A side-effect is state mutated (or changed) outside of the scope of the function.

Example:

counter = 0

def count():
    global counter
    counter += 1
    return counter

count() # 1
count() # 2
count() # 3

Even though we're calling count with the same argument (nothing!), we end up with different output! This is because this function has a side-effect of updating the state of counter, which is outside of its scope. Therefore, this function is not purely functional.

This immutability of state allows us to think in a simpler, and more pure way of avoiding side-effects altogether. And in this design do we find that, already, a lot of bugs start becoming impossible by design and that is truly something to give merit to functional programming for.

However, this does not come without its consequence (as it is a constraint, after all). But like any other constraint in functional programming, there is an elegant workaround to it.

In this article we'll talk about iteration, in the pure functional sense, and realizing how overrated for-loops are.

Recursion

A problem with the aforementioned constraint of immutability, is that some code structures inherently rely on state, such as the for-loop.

for (int i = 0; i < 10; i++) {
    // ...
}

Here's a ubiquitous for-loop construct. We declare some state i, our counter, and then we increment it on every iteration until we fail our condition. Looks good, works pretty well. But the problem lies in how we're relying on mutable state to ensure idempotent behavior.

for (int i = 0; i < 10; i++) {
    i--;
}

When we modify the logic inside of the for-loop (not modifying the for-loop itself), we can introduce bugs such as this one that creates an infinite loop. All because our iteration relies on mutable state.

You might be thinking: "Okay, so for-loops are evil, how are we going to do iterations now?"

Okay no more assumptions on what you're thinking, you're likely more clever than that (or you've read the section header). Here's the answer: Every for-loop can be written recursively.

void loop(const int i) {
    if (i >= 10) return;

    loop(i+1)
}

Oh yeah, computer science! Though significantly more code in an imperative sense, note that it's no longer possible to create the same bug we had in the for-loop without modifying the recursive construct itself, and in that case, skill issue.

Here's that expression in both Haskell and Elixir, which are both functional languages:

loop n
  | n >= 10 = undefined
  | otherwise = loop n+1

def loop(n) when n >= 10, do: nil
def loop(n), do: loop n+1

So much cleaner (and the only way to do standard iteration in these languages).

Do note that although these do the same amount of iteration, they don't actually equal each other exactly. And that's because most for-loops rely on mutable state to be useful. The reason you're probably going to be looping 10 times is imperative, or introduces some side-effect (like printing to standard output). And to make up for that, functional recursions will always have you returning something, the reason you did recursion in the first place, no side-effects.

The Call Stack

If you have ever used recursion before, you will probably be aware of its biggest drawback when compared to iterative constructs, and that is— the call stack.

Every time you enter a function, your program keeps track of it by putting it on the call stack as a stack frame. And when it's done, it simply has to pop that off, and now you're back to the function that called it, and again and again, until you get back to your main function.

This poses as a constraint as maintaining the call stack takes significantly more memory than just keeping track of a counter for iteration. In fact, this leads us to a very common error, the stack overflow.

A stack overflow occurs, when you are in a nested call deeper than what your call stack can handle, and this occurs WAY earlier than an integer overflow (when the computer can no longer represent your big number, so it loops back around to the smallest number), which is the hypothetical bound to our for-loop.

This is problematic, because what if we, for some reason, did need to iterate that many times?

-- haskell
factorial 1 = 1                         -- we set the base case via pattern matching
factorial n = n * factorial (n - 1)

This factorial function would be bounded by the call stack! Not good. This form is what we call head recursion. This is the most common form of recursion, and you'd be forgiven to think that it's the only form of recursion.

The Tail Call Optimization

factorial a 1 = a
factorial a n = factorial (a * n) (n - 1)

This is the same factorial function, but in tail recursive form. Spot the differences. For clarity, here's an imperative example as well:

# head recursive
def factorial(n):
    if n == 1: return 1

    return n * factorial(n-1)

# tail recursive
def factorial_t(a = 1, n):
    if n == 1: return a

    return factorial_t(a * n, n - 1)

The difference in these implementations is that— in tail recursion, we don't need the previous stack frame. We don't need anything from the previous call. We can store all the information we need in our a parameter, which stands for the accumulator (because this is where you accumulate your computation, instead of relying on the call stack).

In fact, we can just re-use our stack frame for our new call. This is called tail-call optimization, a compiler trick done by functional languages (and some imperative languages such as Rust, Lua, and Javascript) wherein it sees that there is no more computation needed after the recursive call, so it reuses the same stack frame. Not only is this much faster, it actually removes the possibility of a stack overflow entirely.

To better understand what it means to no longer have any other computation past the recursive call, think about how when you get to the lowest depth of head recursion, you now have to go back down the call stack, multiplying the accumulated ns while you were nesting calls. But in tail-recursion, you can get your return value (your accumulator) when you get to your final recursive call, no need for traversing the call stack twice.

The most common example of tail-recursion, and is actually just the generalization of it, is the reduce/fold function.

Function Origami

If you are from a Javascript background, you've most likely encountered the reduce function. In fact, you might be familiar with this idiom for summing numbers:

sum = arr => arr.reduce((a,b) => a + b, 0)

reduce is actually (roughly) equivalent to this tail recursive function:

# python (because i don't want to deal with array prototype)

def reduce(arr, fn, acc):
    if len(arr) == 0: return        # base case, no more array

    acc = fn(acc, arr[0])           # apply fn to the head of the array and the accumulator

    return reduce(arr[1:], fn, acc) # recur with the rest of the array and the new accumulator

As we can see, reduce (also known as fold) is just a generalization over a tail recursive function! And you'd be surprised at how many things you can express as a reduce.

reduce/fold gets its name from the fact that it reduces/folds dimensions of an array. Reducing a 2D array yields you a 1D array, and reducing a 1D array yields you an atom (single value). Neat!

Haskell provides us with two standard fold functions, foldr (reduces from the right) and foldl (reduces from the left).

Here are some examples:

sum = foldr (+) 0                   -- partial application
product = foldr (*) 1               -- it doesn't matter whether we use foldr or foldl
any = foldr (||) False              -- because these operations are monoids over their inputs
all = foldr (&&) True               -- (which guarantees associativity)

factorial n = foldr1 (*) [1..n]     -- foldr1 takes the first element as the initial value

-- Folding from the left and prepending the result to an accumulator returns you the reversed array
reverse = foldl (\acc x -> x : acc) []

{-
    ARRAY   |  ACCUMULATOR
    [1 2 3]    [ ]
    [2 3]      [1]
    [3]        [2 1]
    [ ]        [3 2 1]
-}

max = foldr1 compare
    where compare a b           -- a helper function is defined to handle the condition
             | a > b = a
             | otherwise = b

{-
    ARRAY       |  ACCUMULATOR
    [3 4 2 5]       3
    [4 2 5]         3
    [2 5]           4
    [5]             4
    [ ]             5
-}

And here is the imperative pattern that reduce generalizes:

// go

// the input array is of type U because your accumulator doesn't have to be
// the same type as your elements
func reduce[T any, U any](arr []U, fn func(U, T) T, initial T) T {
    result := initial

    for i := 0; i < len(arr); i++ {     // standard for loop syntax used for clarity
        result = fn(arr[i], result)
    }

    return result
}

Best part is, most modern languages that support higher-order functions (Python, Rust, Kotlin, ...) come with a built-in reduce/fold function, so you don't have to implement your own, just have to read documentation :>

Except Go, Go likes to do its own thing.

And that should be it for this part, I figured a break was needed right after the Functors article, so here's one that's a bit more application-oriented. As always, I hope you enjoyed the article, and learned something new!

Functional Patterns: Interfaces and Functors

tyrael — Tue, 02 Jul 2024 17:00:57 +0000

This is part 3 of a series of articles entitled Functional Patterns.

Make sure to check out the rest of the articles!

The Monoid

Compositions and Implicitness

Generics and Typeclasses

To be correct, a function must type-check, and is therefore provable. But in the case of generalized functions, meant to deal with various types, this immediately shows as a pain point. To make a double function work across types, we would have to define them separately!

doubleInt :: Int -> Int
doubleChar :: Char -> Char
doubleFloat :: Float -> Float
-- ...

And for any self-respecting programmer, you should already be finding yourself absolutely appalled by this. We'd just learned about a pattern for building case-handling using partial application but we can't really apply it here since our type signatures won't allow that, and our function has to type-check.

Thankfully, this is already a feature in most modern programming languages. We are allowed to define a generic type. A hypothetical type that only has to verify matching positions in the function signature or variable declarations.

// c++
template <typename T>
T double(T x) {
    return x*2;
}

// rust
fn double<T>(x: T) -> T {
    return x*2;
}

-- haskell
double :: a -> a
double = (*2)       -- partially applied multiplication

And that should solve our problem! As long as the compiler is given these generics, it can figure out what types it has to use at run-time (Rust actually still does this inference at compile-time!).

However, even though there is merit in this implementation— there is still a glaring flaw, that actually gets pointed out by the Haskell compiler, as the above Haskell code actually raises an error.

No instance for ‘Num a’ arising from a use of ‘*’...

We've defined a type, but we aren't always going to be sure this type has the capacity to be doubled. Sure, this immediately works on numbers, but what's stopping the user from calling double on a String? A list? Without a predefined method for doubling these types, they should not be allowed as arguments, in the first place.

So contrary to the name of generics, we're going to have to get a bit more specific, but still general.

This is where typeclasses come in, or also known more commonly in the imperative world as interfaces. Again, if you're using any language that has been made later than C++, you should have access to some implementation of interfaces.

Interfaces, compared to generics, specify some sort of capability of types that can be categorized under it.

Here is a fixed version of our previous code.

double :: (Num a) => a -> a     -- a has to be of typeclass Num
double = (*2)

or in Go:

// We first create an interface that is the union of floats and integers.
type Num interface {
    ~int | ~float64
    // ... plus all other num types
}

func double[T Num](a T) T {
    return a * 2
}

For brevity's sake we'll say that Haskell doesn't really deal with embedded state in their interfaces, such as Typescript's and Go's interfaces (a constraint brought upon by pure functional rules). So even though you might be able to define required attributes of a type to be under an interface, know that pure interfaces only have to define functions or capabilities of the type.

And by capabilities in this context, we are talking about if the type has a dependency in the form of a doubling function— is the compiler taught how to double it?

import Control.Monad (join)

class CanDouble a where
  double :: a -> a

instance CanDouble Int where
  double = (* 2)

instance CanDouble Float where
  double = (* 2)

-- we tell the compiler that doubling a string is concatenating it to itself.
instance CanDouble String where 
  double = join (++)    -- W-combinator, f x = f(x)(x)

And now we're pretty much back to where we were at the start when it comes to code repetition, isn't that funny?

But this fine-grained control of implementation is actually where the power of this comes in. If you've ever heard of the Strategy pattern before, this is pretty much it, in the functional sense.

quadruple :: (CanDouble a) => a -> a
quadruple = double . double

leftShift :: (CanDouble a) => Int -> a -> a
leftShift n e
  | e <= 0 = n
  | otherwise = leftShift (double n) $ e - 1

These functions type-check now, all because we taught the compiler how double types under the CanDouble typeclass.

We can achieve something similar in Go, a big caveat being that we can only define interface methods on non-primitive types. Meaning, we have to define wrapper structs to primitive types.

type CanDouble interface {
    double() CanDouble
}

type String string
type Number interface {
    ~int | ~float64
    // ... plus all other num types
}

type Num[T Number] struct {
    v T
}

func (s String) double() String {
    return s + s
}

func (n Num[T]) double() Num[T] {
    return Num[T]{n.v * 2}
}

func quadruple(n CanDouble) CanDouble {
    return n.double().double()
}

func leftShift(n CanDouble, e uint) CanDouble {
    for i := uint(0); i < e; i++ {
        n = n.double()
    }

    return n
}

This honestly is kind of a bummer, but no worries, as most of the time you're going to be dealing with interfaces will be with custom types and structs.

Functors

Man, that was a lot to take in. Here's a little bit more extra:

A Functor is a type of a function (also known as a mapping) from category to another category (which can include itself, these are called endofunctors).

What this essentially means, is that it is a transformation on some category that maps every element to a corresponding element, and every morphism to a corresponding morphism. An output category based on the input category.

In Haskell, categories that can be transformed by a functor is described by the following typeclass (which also makes it a category in of itself, that's for you to ponder):

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    -- ...

f here is what we call a type constructor. By itself it isn't a concrete type, until it is accompanied by a concrete type. An example of this would be how an array isn't a type, but an array of Int is. The most common form of a type constructor is as a data type (a struct).

From this definition we can surmise that all we need to give to this function fmap is a function (a -> b) (which is our actual functor, don't think about the naming too much), and this would transform a type f a to type f b, a different type in the same category.

Yes, this means Haskell's Functor typeclass is actually a definition for endofunctors, woops!

If all of that word vomit was scary, a very oversimplified version for the requirement of the Functor typeclass is that you are able to map values to other values in the same category.

Arguably the most common Functor we use are arrays:

instance Functor [] where
--  fmap f [] = []
--  fmap f (a:as) = f a : fmap as

    -- simplified
    fmap :: (a -> b) -> [a] -> [b]
    fmap f arr = map f arr

We are able to map an array of [a] to [b] using our function (or functor) f. The typeconstructor of [] serves as our category, and so our functor is a transformation from one type of an array to another.

So, formally: the map function, though commonly encountered nowadays in other languages and declarative frameworks such as React, is simply the application of an endofunctor on the category of arrays.

Wow. That is certainly a description.

Here are more examples of functors in action:

// Go
type Functor[T any] interface {
    fmap(func(T) T) Functor[T]
}

type Pair[T any] struct {
    a T
    b T
}

type List[T any] struct {
    get []T
}

// Applying a functor to a Pair is applying the function
// to both elements
func (p *Pair[T]) fmap(f func(T) T) Pair[T] {
    return Pair[T]{     // apply f to both a and b
        f(p.a),
        f(p.b),
    }
}

func (a *List[T]) fmap(f func(T) T) List[T] {
    res := make([]T, len(a.get))    // create an array of size len(a.get)

    for i, v := range a.get {
        res[i] = f(v)
    }

    return List[T]{res}
}

-- haskell
data Pair t = P (t, t)

instance Functor Pair where
    fmap f (P (x, y)) = P (f x, f y)

So all that it takes to fall under the Functor (again, endofunctor), interface is to have a definition on how to map the contents of the struct to any other type (including its own).

This is another simplifcation, functors also need to have property of identity and composition.

To put simply, whenever you do a map, you're not only transforming the elements of your array (or struct), you're also transforming the functions you are able to apply on this array (or struct). This is what we mean by mapping both objects and morphisms to different matching objects and morphisms in the same category.

This is important to note as even though we end up in the same category (in this context, we map an array, which results in another array), these might have differing functions or implementations available to them (though most of them will be mapped to their relatively equivalent functions, such as a reverse on an array of Int to reverse on an array of Float).

This is where the oversimplifcation kinda messes us up a bit, because if we follow only our definition, we could say that reducing functions such as sum and concat are functors from the category of arrays to atoms, but this isn't necessarily true. As functors also require that you preserve the categorical structure, which won't be covered in this article series as that's way too deeply rooted in category theory.

Apologies if this article contained way more math than applications, but understanding these definitions will help us greatly in understanding the harder patterns later in this series, namely Applicatives and finally Monads.

A monad is a monoid in the category of endofunctors.

We're getting there! :>

Functional Patterns: Composition and Implicitness

tyrael — Mon, 01 Jul 2024 12:50:06 +0000

This is part 2 of a series of articles entitled Functional Patterns.

Make sure to check out the rest of the articles!

The Monoid

Partial Application

Often we talk about currying in an imperative context, it seems unnecessary as it is extra overhead just to be able to deal with multiple arguments.

After all, why should you write a => b => a + b when you can write it with (a, b) => a + b?

And the reason is the main power of currying patterns: Partial Application.

In a non-curried declaration we can really only have:

# Python

def add(a, b):
    return a + b

print(add(4, 5))    # 9
print(add(4, 3))    # 7

But because curried functions return us another function, we can decide to keep it in a partially-applied state.

def add(a):
    return lambda b: a + b

print(add(4)(5))    # 9

# or ...

add4 = add(4)       # A function that takes 1 argument and adds 4
                    # It's a `partially-applied` version of the original `add` function.

print(add4(5))      # 9
print(add4(3))      # 7

Since arguments are handled in separate functions, we can pre-apply some arguments that might fit our use-case without having to rewrite similar logic.

def resize_image(image_type):
    def resize(image, x, y):
        # some extra logic
        return resized_image

    if image_type == "svg":
        # some extra logic 

    return resize

resize_svg  = resize("svg")
resize_png  = resize("png")
resize_jpg  = resize("jpg")
# ...

And now we pretty much have a Builder pattern minus all of the disgusting OOP.

Composition and Combinators

In the functional style, complexity comes from simple functions composed together.

reverse(map(lambda a: a*a, [4,5,3,2]))

# or ...

reverse([a*a for a in [4,5,3,2]])

Here we are squaring all the numbers in an array, and then reversing the resulting array. When we find ourselves saying "and then" after describing what a function does, this is already actually composition! And in a functional paradigm, that's pretty much where all the logic happens, in composition.

Moreover, the type of composition you're probably most accustomed to is actually, what we call a combinator.

Combinators (from the field of mathematics called lambda calculus, and eventually combinatory logic [which is different from combinatorics!]) are patterns which describe the way you are to compose functions together.

In fact, this manner of composition is called the Bluebird (or B-Combinator). The definition is as follows:

// javascript for terse lambdas
B = f => g => a => f(g(a))

And it checks out, the g function is applied first to a, then f is applied to its result!

Let's see an example of the B-combinator in use.

B = lambda f: lambda g: lambda a: f(g(a))

# curried map
c_map = lambda f: lambda a: map(f, a)

# our original composition
reverse(map(lambda a: a*a, [4,5,3,2]))

# The same expression written with the Bluebird
# (spaces are added for clarity)
B (reverse) (c_map(lambda: a*a)) ([4, 5, 3, 2])

And let's add on another combinator called the Thrush combinator, which is pretty useless in imperative programming. All it does is apply a function f to a value a.

T = f => a => f(a)

However, this is an important building block in a pure and lazy functional language such as Haskell, as it allows us to evaluate the function f first, before applying it.

And now we should be able to read all common Haskell syntax!

-- B-Combinator
(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g a = f (g a)

-- T-Combinator
($) :: (a -> b) -> a -> b
($) f a = f a
infixr 0 $  -- the left argument is evaluated first

-- infix versions of functions have the first argument on the left, and the second on the right
-- f . g == (.) f g
ans :: [Int]
ans = reverse . map (\a -> a*a) $ [4, 5, 3, 2]

Okay, well maybe not all syntax, but from inference, we can see where the combinators are used:

The B-Combinator composes reverse and a curried map
The T-Combinator applies the composed function to the array [4, 5, 3, 2]

Even more Combinators!

Composition happens so much in functional programming that mathematicians way smarter than us have actually written down and coined recurring patterns as even more combinators.

Combinators are called combinators because most of them are derived from combining other combinators.

Here are 3 combinators that are notable in my opinion (the rest is left for curious readers to read up on :>).

The Phi Combinator

phi = f => g => h => a => f (g(a)) (h(a))

Function f is called with the arguments g(a) and h(a), or the result of calling g and h on a value a separately.

A great example of this pattern would be the average function.

phi = lambda f: lambda g: lambda h: lambda a: f (g(a)) (h(a))

a = [1, 2, 3, 4, 5]

div = lambda a: lambda b: a / b     # helper division function

print( sum(a) / len(b) )            # we can see the pattern emerge here
                                    # if we think of division as a function

average = phi (div) (sum) (len) (a)
print(average)

-- haskell
import Control.Applicative

-- liftA2 is Haskell's phi combinator
average = liftA2 div sum length [1 .. 5]

The Psi Combinator

psi = f => g => a => b => f (g(a)) (g(b))

Function f is called with the arguments g(a) and g(b), or the result of calling g on value a and b separately.

There are two good examples that come to mind.

// javascript
psi = f => g => a => b => f (g(a)) (g(b))

eq = a => b => a == b   // helper function for checking equality

// A simple way to compare arrays in javascript is to turn *both* of them into strings first.
a = [2, 3, 4]
b = [3, 4, 5]

console.log( JSON.stringify(a) == JSON.stringify(b) )

console.log( psi (eq) (JSON.stringify) (a) (b) )

// The distance formula has you square *both* differences first, and then sqrt the sum.
distanceFormula = (x2, x1, y2, y1) => {
    return psi (a => b => Math.sqrt(a + b)) (a => a * a) (x2 - x1) (y2 - y1))
}

-- haskell
import Data.Function

-- `on` is Haskell's infix version of Psi
eqArr = ((==) `on` show) [2,3,4] [3,4,5]

distanceFormula x2 x1 y2 y1 = (sqrt .: ((+) `on` (^2))) (x2 - x1) (y2 - y1)

The Starling (S-Combinator)

s = f => g => a => f (a) (g(a))

Function f is called with the arguments a and g(a), the result of calling g on value a.

For the ones with keen eyes, you can already probably notice that the S-Combinator is actually just a special form of the Phi combinator. And that's because it is. Specifically, it is the Phi combinator with g as the identity function (or the I-Combinator) defined as:

i = a => a          // the identity combinator simply returns its argument

s = f => g => a => phi (f) (i) (g) (a)

A great example would be checking if a string is a palindrome, wherein we compare a string to its reverse.

# python
s = lambda f: lambda g: lambda a: f (a) (g(a))

eq = lambda a: lambda b: a == b     # curried helper

s (eq) (reverse) ("racecar")

-- haskell
ans :: Bool
ans = ((==) <*> reverse) "racecar"   -- (<*> is Haskell's infix version for the S-combinator)

Implicitness

Using compositions and combinators allow us to write functions with implicit arguments. This is called its tacit or point-free form.

This means we no longer have to specify the arguments of our functions, as they are implicitly declared by the compositions we use, leaving us with a partially applied function.

sqr = lambda a: a*a # helper for squaring
c_map = lambda f: lambda a: map(f, a)

# Explicit form
def _sum_of_squares(arr : list[int]) -> int:
    squares = map(sqr, arr)
    return sum(squares)

# Implicit form
sum_of_squares = b (sum) (c_map(sqr))   # Note that we aren't providing the `arr` argument

sum_of_squares([1,2,3]) # But we can still use it because sum_of_squares is partially applied

And this is how functional languages can get away with elegant point-free definitions. In fact, one of my favorite things to do when writing in functional languages is to refactor them into their tacit forms.

import Control.Applicative
import Data.Function

sumOfSquares :: [Int] -> Int
sumOfSquares = sum . map (^2)

isPalindrome :: String -> Bool
isPalindrome = (==) <*> reverse

isLonger :: String -> String -> Bool
isLonger = (>) `on` length

average :: [Int] -> Float
average = liftA2 (/) (sum) (length)

Tacit definitions of course bring extra overhead to your code, but like many things in modern programming, they can serve as abstractions for programmers to be able to write terse and (subjectively) clean code by leveraging math.

Applying functional patterns in mostly imperative languages don't really end up that nice-looking but I still hope you learned something new from this, and are able to apply the patterns in this article (probably not in production codebases) to your future code!

Functional Patterns: The Monoid

tyrael — Sat, 29 Jun 2024 13:44:18 +0000

Trigger Warning: this article contains Haskell codeblocks!

Introduction

As a programmer, I've always found myself obssessing over patterns I
could find in the code I write. From simple ones such as the Gaussian
sum and early returns, to ones that hold a bit more complexity such as the Strategy pattern.

I find satisfaction in finding elegant ways to express recurring needs and results, which has ultimately led me to my exploration of the Functional Programming paradigm. And so, early in 2023, in my freshman year of college, I decided to undergo the massive undertaking that is, learning Haskell.

I'm not going to bore you on the details that is learning a language which is meant to unapologetically academic as I believe I am still not that good at it yet, but I have picked up the patterns that I had been searching for in the first place, which is a win in my book.

I plan to have this as the first article of more elegant patterns I've found
from my months of studying functional programming.

Types and Categories

I'll try to save you from the incredibly white-paper definitions (I'm looking at you, category theory), so some of the definitions you encounter in these articles may be oversimplifications and I encourage the reader to research more on it for a deeper (and more correct) understanding.

A recurring theme amongst functional languages (or ones that implement a lot of rules present in pure functional languages such as Rust)— is the presence of type safety and how, most of the time, the functions themselves are correct (also known as provable), as long it type checks.

Not only does this make several bugs impossible by design, we can find that from this emerges entirely new patterns that we can take advantage of (at the cost of a little bit more overhead, of course).

Let's take a look at a function signature for the abs (a common name for the absolute value function) function, from Haskell:

-- function bodies won't be defined unless they are relevant
abs :: Int -> Int
abs n = undefined

and its equivalent signature in a language like Go:

func abs (n int) int {
    // function bodies won't be defined unless they are relevant
    panic()
}

We can see that Haskell's -> gives us a pretty good idea of what a function does.

It takes an Int and returns another Int.

Moreover, we see that this function only takes one argument, and therefore can be referred to as a unary function.

Let's take a look at an example for a binary function.

add :: Int -> Int -> Int
add a b = a + b

And what should be its equivalent Go function:

func add(a, b int) int {
    return a + b
}

That's odd, we can see that Haskell's signature requires a bit more of thinking to understand, and you'd be forgiven for thinking this signature meant:

A function that takes an Int and returns an Int that returns an Int.

But this actually has something to do with how it deals with multi-variable functions under the hood. This is due to an inherent constraint in pure functional languages, that is:

A function always take one argument and returns one result.

And as you can tell, it does its job as a constraint really well because— well, it is very constraining. However, this can be worked around using this pattern called currying.

This is the actual equivalent of the Haskell code in Go code:

func add(a int) func(int) int {
    return func (b int) int {
        return a + b
    }
}

Or a terser equivalent in Javascript:

a => b => a + b

Aha! There are two functions, one for each argument! And because the second function is declared inside the first one, it can access the a. This is called a closure.

So what's really happening in the Haskell signature is:

add :: Int -> (Int -> Int)

Our add function takes an Int, then returns another function that takes an Int and returns an Int! Currying!

Lastly, to demonstrate type-correctness here's another example:

-- takes:
-- * some unary function (a -> b)
-- * list of a
--
-- returns:
-- * a list of b
map :: (a -> b) -> [a] -> [b]

sqr :: Int -> Int

sum :: [Int] -> Int

sumOfSquares :: [Int] -> Int
sumOfSquares = sum . map sqr

We can prove the type of sumOfSquares by following the types of the composed functions in its definition.

sqr takes an Int returns an Int
- At this point our signature is: Int -> Int
map takes a function from some type a (in this case Int) and turns it into some type b (in this case, still Int), and also takes a list of Int
- At this point our signature is: [Int] -> [Int]
  - Notice how we are not asking for an (a -> b), as this is curried into map by providing it the argument of sqr.
  - We are now returning the [a] -> [b] part of the signature.
The result of map is then "piped" into sum, which takes a list of Int, returning an Int.
- We finally reach our final signature of [Int] -> Int!

The Monoid

A type is said to be a Monoid over some binary function or operation if the result remains within the domain of the type, AND there exists an identity element.

Or essentially, you have some binary function f over some type a,
meaning both arguments of f be of type a, and the result is still of type a. And there exists an element of type a that when applied to any other element of type a over f, results in the same element.

And to another degree of simplification: if you call the function f with two arguments of type a, the result should be of type a. And there should exist a value of type a, which we will call the identity element, that when provided as an argument— will return the other argument in the call.

Here are some examples of Monoids:

We can say Int is a Monoid over + (addition) because whatever two Ints we add will always yield another Int.
- The identity element of this Monoid would be the number 0, as adding 0 to any Int will give you the same Int.
We can say Int is a Monoid over * (multiplication) because whatever two Ints we multiply, will always yield another Int.
- The identity element of this Monoid would be the number 1, as multiplying 1 to any Int will give you the same Int.
We can't say Int is a Monoid over / (division) because there exists division operations between two Ints that do not yield an Int (i.e. 1 / 2)

A useful property of monoids is that— as long as you are only applying functions to a type in which in it is a Monoid over, you can easily guarantee type safety, as everything remains in the same type.

(+) :: Int -> Int -> Int
(*) :: Int -> Int -> Int

incrementNumber :: Int -> Int
incrementNumber a = 4 * 5 + 3 + a

As you can see, both operations share the same signature and the resulting type is the same as the input type, and this is because they are a Monoid over the two composed functions guaranteeing the same type is returned.

Usage

Goes without saying, there will be other uses for Monoids that you might encounter yourself, and so I'll leave that to you to discover yourself :>

Let's say we are creating an Auto Moderator that filters characters from chat messages based on arbitrary predicates set by us, the developer. Essentially, we want to run several checks and make sure a character passes all of them.

Let's take a look at the signatures of the predicates we will be using:

isBraille :: Char -> Bool
isUpper :: Char -> Bool
isNumber :: Char -> Bool
isEmoji :: Char -> Bool

Very strange predicates for a chatting service indeed. But from these
signatures, we cannot immediately see where the Monoid pattern applies, after all none of these take the same type as the type it returns!

So let's apply the naive solution to this problem.

isValid :: Char -> Bool
isValid c = not (isBraille c || isUpper c || isNumber c || isEmoji c)

Disgusting and abhorrent. This degree of repetition in code should already be raising some alarms for you.

Let's think it over again, what do we really need here? We need some function (Char -> Bool) that acts as the disjunction of all the (Char -> Bool)s we have.

Let's take a look at the signature for the -> function (yes, it is a function as well).

type (->) :: * -> * -> *  -- this just means it is not a concrete type
                          -- it needs 2 concrete types to be one.
                          -- i.e (Char -> Bool) is a type but (Char ->) is not.

-- ...

instance Monoid b => Monoid (a -> b) -- important!

There it is! This instance signature states, that if the return of a function is a Monoid, the entire function is a Monoid! And this definition does not have any conflict with our definitions we've previously established.

And if you think about it, a Bool is actually a Monoid over disjunction! For any boolean you perform a logical OR on, you will always get another boolean.

Moreover, if you logical OR any boolean with False, you will end up with the same boolean, fulfilling the condition for an identity element!

And the last piece of our puzzle, the Haskel's fold function. Let's take a look at its signature.

import Data.Foldable

fold :: (Foldable t, Monoid m) => t m -> m

What this means for our context is that the fold function requires a list (which falls under the Foldable constraint) of our Monoid type.

However, to define a proper Monoid type, we have to specify what it is a Monoid over (Boolean is a Monoid over all logical operators). Thankfully, this is already done for us by Haskell, by its Any (Monoid over logical OR) wrapper.

And so we're left with:

import Data.Monoid
import Data.Foldable

isBraille :: Char -> Bool
isUpper :: Char -> Bool
isNumber :: Char -> Bool
isEmoji :: Char -> Bool

isValid :: Char -> Bool
isValid = not . getAny . fold predicates
    where predicates = map (Any .) [isBraille, isUpper, isNumber, isEmoji]

First, we convert all of our list of (Char -> Bool) to a list of (Char -> Any) by using a map (Any .).

So now we have a list of (Char -> Any), which if you remember, is now a list of Monoids that can be combined into one (Char -> Any) using fold, which is equal to applying them one after another!

NOTE: The Monoid's binary function is associative, meaning it can be applied in any order.

And then lastly, we extract our value from the Any wrapper, and then negate it with not. And now we have a much more elegant solution.

Equivalent Go code:

func isValid(c rune, predicates []func(rune) bool) bool {
    result = false  // our identity element

    // fold over our Monoid
    for _, predicate := range predicates {

        if result = result || predicate(c); result {
            break;  // early return on first true (also done by Haskell under the hood)
        }
    }

    return !result
}

And that should be it! I hope you learned something new from this article, and maybe even get to apply this pattern in your future coding endeavours.

DEV Community: tyrael

Tangible Correctness

When not to test

Factories, fixtures, and faking

Automate tests

Use AI

Conclusion

In defense of `union` and `goto`

Undefined behavior

union and goto

Unions

Tagged unions

More on C's tagged unions

goto

Conclusion

Figma for Programmers

Preparing your palette, literally

On divs and flexboxes

Components and variants

Conclusion

Rust-like Iteration in Lua

Leveraging state

Metatables

Implementations

Lua as your favorite Programming Language

Simplicity

Tables

Homebrewing

Usecases

Conclusion

Understanding Python Iterables: Generators

Iterators

Generators

Laziness

Functional Patterns: The Monad

What's the problem?

In the Category of Endofunctors

A Monoid

Monads in Practice

Imperatively speaking,

Functional Patterns: Zips and the Applicative

Functor Recap

Zips

Applicatives

The Maybe Monad

The ZipList Applicative

Functional Patterns: Recursions and Reduces

State

Recursion

The Call Stack

The Tail Call Optimization

Function Origami

Functional Patterns: Interfaces and Functors

Generics and Typeclasses

Categories

Functors

Functional Patterns: Composition and Implicitness

Partial Application

Composition and Combinators

Even more Combinators!

Implicitness

Functional Patterns: The Monoid

Introduction

Types and Categories

The Monoid

Usage

`union` and `goto`

`goto`

On `div`s and `flexbox`es