Collections and Data Structures

/**
 * List with guaranteed non-empty contents
 */
data class NonEmptyList<out A>(
    val head: A,
    val tail: List<A>
) {
    val size: Int
    val indices: IntRange
}

/**
 * Create NonEmptyList from head and tail elements
 */
fun <A> nonEmptyListOf(head: A, vararg tail: A): NonEmptyList<A>

/**
 * Create NonEmptyList from single element
 */
fun <A> A.nel(): NonEmptyList<A>

// Safe construction
val numbers = nonEmptyListOf(1, 2, 3, 4, 5)
val single = 42.nel()

// Safe head access - no null checks needed
val first = numbers.head  // Always safe: 1
val remaining = numbers.tail  // [2, 3, 4, 5]

// Size is always >= 1
val count = numbers.size  // 5

/**
 * Transform each element, preserving non-empty structure
 */
fun <A, B> NonEmptyList<A>.map(f: (A) -> B): NonEmptyList<B>

/**
 * Monadic bind for NonEmptyList
 */
fun <A, B> NonEmptyList<A>.flatMap(f: (A) -> NonEmptyList<B>): NonEmptyList<B>

/**
 * Filter elements, may return empty list
 */
fun <A> NonEmptyList<A>.filter(predicate: (A) -> Boolean): List<A>

/**
 * Filter elements, keeping only Some results
 */
fun <A, B> NonEmptyList<A>.mapNotNull(f: (A) -> B?): List<B>

/**
 * Reverse the list order
 */
fun <A> NonEmptyList<A>.reverse(): NonEmptyList<A>

/**
 * Remove duplicate elements
 */
fun <A> NonEmptyList<A>.distinct(): NonEmptyList<A>

val words = nonEmptyListOf("hello", "world", "arrow")

// Transform while preserving structure
val lengths = words.map { it.length }  // NonEmptyList(5, 5, 5)
val uppercase = words.map { it.uppercase() }  // NonEmptyList("HELLO", "WORLD", "ARROW")

// Flat mapping
val characters = words.flatMap { word -> 
    word.toCharArray().toList().toNonEmptyListOrNone().getOrElse { 'x'.nel() }
}

// Filtering (returns regular List since result might be empty)
val longWords = words.filter { it.length > 4 }  // List("hello", "world", "arrow")

/**
 * Left-associative fold
 */
fun <A, B> NonEmptyList<A>.foldLeft(b: B, f: (B, A) -> B): B

/**
 * Right-associative fold with lazy evaluation
 */
fun <A, B> NonEmptyList<A>.foldRight(
    lb: Eval<B>, 
    f: (A, Eval<B>) -> Eval<B>
): Eval<B>

/**
 * Reduce using the same type (no initial value needed)
 */
fun <A> NonEmptyList<A>.reduce(f: (A, A) -> A): A

/**
 * Concatenate with another NonEmptyList
 */
fun <A> NonEmptyList<A>.plus(other: NonEmptyList<A>): NonEmptyList<A>

/**
 * Concatenate with regular List
 */
fun <A> NonEmptyList<A>.plus(other: List<A>): NonEmptyList<A>

/**
 * Append single element
 */
fun <A> NonEmptyList<A>.plus(element: A): NonEmptyList<A>

/**
 * Prepend single element
 */
fun <A> NonEmptyList<A>.cons(element: A): NonEmptyList<A>

/**
 * Zip with another NonEmptyList
 */
fun <A, B> NonEmptyList<A>.zip(other: NonEmptyList<B>): NonEmptyList<Pair<A, B>>

/**
 * Zip with transformation function
 */
fun <A, B, C> NonEmptyList<A>.zip(
    other: NonEmptyList<B>, 
    f: (A, B) -> C
): NonEmptyList<C>

/**
 * Convert to regular List
 */
fun <A> NonEmptyList<A>.toList(): List<A>

/**
 * Convert List to NonEmptyList safely
 */
fun <A> List<A>.toNonEmptyListOrNull(): NonEmptyList<A>?

/**
 * Convert List to Option<NonEmptyList>
 */
fun <A> List<A>.toNonEmptyListOrNone(): Option<NonEmptyList<A>>

val list1 = nonEmptyListOf(1, 2, 3)
val list2 = nonEmptyListOf(4, 5, 6)

// Combination
val combined = list1 + list2  // NonEmptyList(1, 2, 3, 4, 5, 6)
val withExtra = list1 + listOf(7, 8)  // NonEmptyList(1, 2, 3, 7, 8)
val withSingle = list1 + 9  // NonEmptyList(1, 2, 3, 9)

// Zipping
val pairs = list1.zip(list2)  // NonEmptyList(Pair(1,4), Pair(2,5), Pair(3,6))
val sums = list1.zip(list2) { a, b -> a + b }  // NonEmptyList(5, 7, 9)

// Safe conversions
val regularList = listOf(1, 2, 3)
val maybeNel = regularList.toNonEmptyListOrNone()  // Some(NonEmptyList(1, 2, 3))

val emptyList = emptyList<Int>()
val empty = emptyList.toNonEmptyListOrNull()  // null

/**
 * Set with guaranteed non-empty contents
 */
data class NonEmptySet<out A>(
    val head: A,
    val tail: Set<A>
) {
    val size: Int
}

/**
 * Create NonEmptySet from head and tail elements
 */
fun <A> nonEmptySetOf(head: A, vararg tail: A): NonEmptySet<A>

/**
 * Check if element is contained in the set
 */
fun <A> NonEmptySet<A>.contains(element: A): Boolean

/**
 * Add element to set (always returns NonEmptySet)
 */
fun <A> NonEmptySet<A>.plus(element: A): NonEmptySet<A>

/**
 * Union with another NonEmptySet
 */
fun <A> NonEmptySet<A>.plus(other: NonEmptySet<A>): NonEmptySet<A>

/**
 * Transform each element, preserving non-empty structure
 */
fun <A, B> NonEmptySet<A>.map(f: (A) -> B): NonEmptySet<B>

/**
 * Monadic bind for NonEmptySet
 */
fun <A, B> NonEmptySet<A>.flatMap(f: (A) -> NonEmptySet<B>): NonEmptySet<B>

/**
 * Convert to regular Set
 */
fun <A> NonEmptySet<A>.toSet(): Set<A>

val colors = nonEmptySetOf("red", "green", "blue")

// Safe operations
val hasRed = colors.contains("red")  // true
val withYellow = colors + "yellow"  // NonEmptySet("red", "green", "blue", "yellow")

// Transformations
val lengths = colors.map { it.length }  // NonEmptySet(3, 5, 4)
val uppercased = colors.map { it.uppercase() }  // NonEmptySet("RED", "GREEN", "BLUE")

/**
 * Sequence a collection of Either values
 */
fun <E, A> Iterable<Either<E, A>>.sequence(): Either<E, List<A>>

/**
 * Sequence a collection of Option values
 */
fun <A> Iterable<Option<A>>.sequence(): Option<List<A>>

/**
 * Flatten collection of Either values, accumulating errors
 */
fun <E, A> Iterable<Either<E, A>>.flattenOrAccumulate(): Either<NonEmptyList<E>, List<A>>

/**
 * Traverse collection with function returning Either
 */
fun <A, B, E> Iterable<A>.traverse(f: (A) -> Either<E, B>): Either<E, List<B>>

/**
 * Traverse collection with function returning Option
 */
fun <A, B> Iterable<A>.traverse(f: (A) -> Option<B>): Option<List<B>>

// Sequence Either values
val results = listOf(1.right(), 2.right(), 3.right())
val sequenced = results.sequence()  // Either.Right([1, 2, 3])

val mixed = listOf(1.right(), "error".left(), 3.right())
val failed = mixed.sequence()  // Either.Left("error")

// Accumulate errors
val accumulated = mixed.flattenOrAccumulate()  // Either.Left(NonEmptyList("error"))

// Traverse with parsing
val strings = listOf("1", "2", "3")
val parsed = strings.traverse { s -> 
    Either.catch { s.toInt() }.mapLeft { "Parse error: $s" }
}  // Either.Right([1, 2, 3])

/**
 * Shorter alias for NonEmptyList
 */
typealias Nel<A> = NonEmptyList<A>

/**
 * Shorter alias for NonEmptySet  
 */
typealias Nes<A> = NonEmptySet<A>