This content originally appeared on DEV Community and was authored by Depa Reddy
In this short tutorial we will implement A Generic Foldable Type Class in Scala: From Lists to Custom Tuple Types.We will cover key concepts such as type lambdas, type classes, type class instances, and extension methods.full code can be found at this gist FoldableInstances.scala
Type lambdas in code
Type lambdas in Scala are a way to define anonymous type-level functions. They allow you to create new types on the fly by applying transformations to existing types.
This is particularly useful when working with higher-kinded types (types that take other types as parameters, like List, Option, or Either).
The syntax for a type lambda in Scala is
type TypeLambda = [Param1, Param2, ...] =>> ResultType
- Type Alias: TupleMy2
TupleMy2 is defined as:
type TupleMy2 = [X] =>> (X, X)
This means:
TupleMy2 is a type-level function that takes a single type parameter X.
It produces a tuple type (X, X) where both elements of the tuple are of type X.
For example:
If X is Int, then TupleMy2[Int] is (Int, Int).
If X is String, then TupleMy2[String] is (String, String).
This allows us to generalize folding operations over both lists and tuples.
Defining the Foldable Type Class
Type classes are a powerful and flexible feature in Scala that allow you to define generic behavior that can be applied to different types without modifying those types
In below provided code, the Foldable trait is a type class that abstracts the concept of "foldability" for different data structures.
Foldable is a type class parameterized by a higher-kinded type C[_]
In this example, Foldable is a type class that defines a method foldr for that types must implement to be considered "foldable."
trait Foldable[C[_]]:
def foldr[A, B](xs: C[A])(init: B)(fx: (A, B) => B): B
Create Type Class Instances
Now, we can create instances of the Foldable type class for different types:
In scala The given keyword helps define type class instances that the compiler can inject automatically.
Here we creates type class instance for specific types (List and TupleMy2)
Each instance provides a concrete implementation of foldr
Instances are named (listFoldable, tuple2Foldable) but names are optional
given listFoldable: Foldable[List] with
override def foldr[A, B](xs: List[A])(init: B)(fx: (A, B) => B): B =
xs.foldRight(init)(fx)
given tuple2Foldable: Foldable[TupleMy2] with
override def foldr[A, B](xs: TupleMy2[A])(init: B)(fx: (A, B) => B): B =
fx(xs._1, fx(xs._2, init))
List Instance:Uses List's built-in foldRight to implement foldr.
Example: List(1, 2, 3).foldRight(0)(_ + _) sums the elements.
Tuple Instance:For a tuple (a, b), applies fx to b and init first, then to a and the result.
Example: ("a", "g").foldRight("init")(_ + _) produces "initga".
Extension Methods: FoldableOps
The extension keyword is used to define an extension method. This allows you to add methods to existing types without modifying their source code.
its purpose is to add a foldRight method to any type with a Foldable instance.
object FoldableOps:
extension [C[_], A](xs: C[A])(using foldable: Foldable[C])
def foldRight[B](init: B)(fx: (A, B) => B) =
summon[Foldable[C]].foldr(xs)(init)(fx)`
Components of the Extension Method
- Extension Method Definition:
The syntax
extension [C[_], A](xs: C[A])indicates that this extension method applies to any type constructor C that takes one type parameter (like List, Option, etc.) and to any type A. - Using Clause:
The
(using foldable: Foldable[C])part indicates that this method requires an implicit Foldable[C] instance to be available in the scope. This is crucial because the method relies on the foldr implementation provided by the Foldable type class. - Method Implementation:
The method
foldRight[B](init: B)(fx: (A, B) => B)takes two parameters: init: The initial value of type B for the fold operation. fx: A function that takes an element of type A and an accumulator of type B, returning a new accumulator of type B. Inside the method,summon[Foldable[C]]is called to retrieve the implicit Foldable[C] instance. This instance is then used to call the foldr method, passing in the collection xs, the initial value init, and the folding function fx.
How It Works in Practice:
// For List
List("a", "b").foldRight("init")(_ + _)
// For Tuple
("a", "g").foldRight("init")(_ + _)
When you call foldRight on a List or TupleMy2, Scala will automatically look for an appropriate Foldable instance based on the type of the collection:
For List("a", "b"), the compiler finds the listFoldable instance because List is a type that has a Foldable instance defined.
For stringTuple, which is of type TupleMy2[String], the compiler finds the tuple2Foldable instance.then it Injects the instance implicitly into the foldRight call.
Brings all given instances from FoldableInstances into scope,like this.Required for the compiler to find the instances during implicit resolution
import com.example.FoldableInstances.given
Extension Method Execution:
summon[Foldable[List]].foldr(List("a", "b", "c", "d"))("init")((x, acc) => acc + x)`
The foldRight method is executed, and the compiler translates the call to summon[Foldable[C]] retrieves the instance from implicit scope.The foldr method of the listFoldable instance is called, performing the fold operation
Test Code
- Folding a List
val list = List("a", "b", "c", "d").foldRight("init")((x, a) => a + x)
println("list" + list) // Output: "listinitdcba"
Behavior: Folds the list from right to left, appending elements to init.
Steps:
- Start with "init".
- Process "d" → "initd".
- Process "c" → "initdc".
- Process "b" → "initdcb".
Process "a" → "initdcba".
Folding a Tuple
Behavior: Folds the tuple ("a", "g") from right to left.
Steps:
- Start with "init".
- Process "g" → "initg".
- Process "a" → "initga".
Key Flow
- Define Type Class: Foldable trait with required operations
- Provide Instances: Implementations for specific types using given
- Import Instances: Make instances available in current scope
- Use via Extension: Call methods that require the type class instance
- Compiler Resolution: Automatically selects correct instance based on type
. Key Concepts
- Type Classes: Foldable abstracts folding logic for different containers.
- Higher-Kinded Types: C[_] generalizes over types like List and TupleMy2.
- Type Lambdas: TupleMy2 is defined as a type-level function for tuples.
- Extension Methods: Enable syntax like container.foldRight(... )
This content originally appeared on DEV Community and was authored by Depa Reddy
Depa Reddy | Sciencx (2025-02-09T17:47:15+00:00) Implementing a Generic Foldable Type Class in Scala with List and Tuple Instances. Retrieved from https://www.scien.cx/2025/02/09/implementing-a-generic-foldable-type-class-in-scala-with-list-and-tuple-instances/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.