纯函数式Scala自定义泛型列表构建及foldRight报错修复求助

Let's walk through fixing your implementation and building a proper pure-functional generic list that aligns with your requirements. The core issues in your original code were incorrect type parameters in foldRight, impure constructs like while loops, unnecessary side effects, and misaligned pattern matching.

Key Fixes & Approach #

1. Correct foldRight Signature: Your original foldRight used mismatched type parameters leading to casting errors. We'll use a proper signature that maps list elements of type A to an accumulated value of type B.
2. Pure Functional foldLeft: Replace mutable loops with tail-recursive logic to keep everything functional.
3. Fold-Based Operations: Implement map, append, and length using foldRight (per the idea that fold can replace data type constructors).
4. Encapsulate Constructors: Make Cons and Nil private to enforce using the companion object's safe constructors.
5. Remove Side Effects: Eliminate println calls from core list methods—pure functions shouldn't have side effects.

Corrected Implementation #

import scala.annotation.tailrec
import scala.util.control.NoStackTrace

sealed trait myList[+A] {
  // Core foldRight implementation: traverses from right to left
  def foldRight[B](z: B)(f: (A, B) => B): B

  // Tail-recursive foldLeft (pure functional, no mutable state)
  def foldLeft[B](z: B)(f: (B, A) => B): B = {
    @tailrec
    def loop(current: myList[A], acc: B): B = current match {
      case Nil => acc
      case Cons(h, t) => loop(t, f(acc, h))
    }
    loop(this, z)
  }

  // Alias fold to foldLeft (common convention)
  def fold[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f)

  // Map implemented via foldRight
  def map[B](f: A => B): myList[B] =
    foldRight(myList.empty[B])((elem, acc) => myList.cons(f(elem), acc))

  // Append implemented via foldRight
  def append[B >: A](elem: B): myList[B] =
    foldRight(myList.cons(elem))((current, acc) => myList.cons(current, acc))

  // Length calculated via foldRight
  def length: Int =
    foldRight(0)((_, acc) => acc + 1)

  def isEmpty: Boolean = this == Nil

  def head: A = this match {
    case Nil => throw EmptyListException("Cannot get head of empty list")
    case Cons(h, _) => h
  }

  def tail: myList[A] = this match {
    case Nil => throw EmptyListException("Cannot get tail of empty list")
    case Cons(_, t) => t
  }

  // Human-readable string representation
  override def toString: String = {
    val elements = foldLeft(List.empty[String])((acc, elem) => elem.toString :: acc).reverse.mkString(", ")
    s"myList($elements)"
  }
}

// Private empty list implementation
private case object Nil extends myList[Nothing] {
  override def foldRight[B](z: B)(f: (Nothing, B) => B): B = z
}

// Private non-empty list implementation
private case class Cons[+A](h: A, t: myList[A]) extends myList[A] {
  override def foldRight[B](z: B)(f: (A, B) => B): B = f(h, t.foldRight(z)(f))
}

// Companion object for safe list construction
object myList {
  def empty[A]: myList[A] = Nil

  // Smart constructor for non-empty lists
  def cons[A](head: A, tail: myList[A] = empty[A]): myList[A] = Cons(head, tail)

  // Create list from variable arguments using foldRight
  def apply[A](elems: A*): myList[A] =
    elems.foldRight(empty[A])((elem, acc) => cons(elem, acc))
}

// Custom exception for empty list operations
case class EmptyListException(message: String) extends RuntimeException(message) with NoStackTrace

// Example domain class (Scala convention: PascalCase for class names)
case class Truck(numberPlate: String)

// Test main
object Main {
  def main(args: Array[String]): Unit = {
    val truck1 = Truck("1233bsd")
    val truck2 = Truck("dsads334")
    
    // Create list using companion object
    val myTrucks = myList(truck1, truck2)
    
    println("Original list:")
    println(myTrucks) // Output: myList(Truck(1233bsd), Truck(dsads334))
    
    println("\nList length:")
    println(myTrucks.length) // Output: 2
    
    println("\nCopied list via foldRight:")
    val copiedList = myTrucks.foldRight(myList.empty[Truck])((truck, acc) => myList.cons(truck, acc))
    println(copiedList) // Output: myList(Truck(1233bsd), Truck(dsads334))
    
    println("\nMapped list (format plate numbers):")
    val formattedTrucks = myTrucks.map(t => Truck(t.numberPlate.toUpperCase))
    println(formattedTrucks) // Output: myList(Truck(1233BSD), Truck(DSADS334))
  }
}

Explanation #

• Fold as Constructor Replacement: By implementing most operations via foldRight, we avoid direct pattern matching on Cons/Nil in user code, aligning with the idea that fold can act as a replacement for data type constructors.
• Encapsulation: Cons and Nil are private, so users can only build lists using myList.apply or myList.cons, preventing misuse of internal implementation details.
• Pure Functional: No mutable variables, no side effects in core list methods—all operations return new lists instead of modifying existing ones.
• Type Safety: Correct type parameters ensure no casting errors, and the custom exception provides clear error messages for empty list operations.

内容的提问来源于stack exchange，提问作者donald