f# - Actualización de estructuras de datos inmutables anidadas.
functional-programming (5)
Quiero actualizar una estructura de datos anidada e inmutable (adjunto un pequeño ejemplo de un juego hipotético) y me pregunto si esto se puede hacer de una manera un poco más elegante.
Cada vez que algo dentro de la mazmorra cambia, necesitamos una nueva mazmorra, así que le di un miembro de actualización general. La mejor manera de usar esto, que podría encontrar para el caso general, es especificar las funciones de procesamiento para cada anidación y luego pasar la función combinada al miembro de actualización.
Luego, para casos realmente comunes (como aplicar un mapa a todos los monstruos en un nivel específico), proporciono miembros adicionales (Dungeon.MapMonstersOnLevel).
Todo funciona, me gustaría saber si alguien puede pensar en mejores formas de hacerlo.
¡Gracias!
// types
type Monster(awake : bool) =
member this.Awake = awake
type Room(locked : bool, monsters : Monster list) =
member this.Locked = locked
member this.Monsters = monsters
type Level(illumination : int, rooms : Room list) =
member this.Illumination = illumination
member this.Rooms = rooms
type Dungeon(levels : Level list) =
member this.Levels = levels
member this.Update levelFunc =
new Dungeon(this.Levels |> levelFunc)
member this.MapMonstersOnLevel (f : Monster -> Monster) nLevel =
let monsterFunc = List.map f
let roomFunc = List.map (fun (room : Room) -> new Room(room.Locked, room.Monsters |> monsterFunc))
let levelFunc = List.mapi (fun i (level : Level) -> if i = nLevel then new Level(level.Illumination, level.Rooms |> roomFunc) else level)
new Dungeon(this.Levels |> levelFunc)
member this.Print() =
this.Levels
|> List.iteri (fun i e ->
printfn "Level %d: Illumination %d" i e.Illumination
e.Rooms |> List.iteri (fun i e ->
let state = if e.Locked then "locked" else "unlocked"
printfn " Room %d is %s" i state
e.Monsters |> List.iteri (fun i e ->
let state = if e.Awake then "awake" else "asleep"
printfn " Monster %d is %s" i state)))
// generate test dungeon
let m1 = new Monster(true)
let m2 = new Monster(false)
let m3 = new Monster(true)
let m4 = new Monster(false)
let m5 = new Monster(true)
let m6 = new Monster(false)
let m7 = new Monster(true)
let m8 = new Monster(false)
let r1 = new Room(true, [ m1; m2 ])
let r2 = new Room(false, [ m3; m4 ])
let r3 = new Room(true, [ m5; m6 ])
let r4 = new Room(false, [ m7; m8 ])
let l1 = new Level(100, [ r1; r2 ])
let l2 = new Level(50, [ r3; r4 ])
let dungeon = new Dungeon([ l1; l2 ])
dungeon.Print()
// toggle wake status of all monsters
let dungeon1 = dungeon.MapMonstersOnLevel (fun m -> new Monster(not m.Awake)) 0
dungeon1.Print()
// remove monsters that are asleep which are in locked rooms on levels where illumination < 100 and unlock those rooms
let monsterFunc2 = List.filter (fun (monster : Monster) -> monster.Awake)
let roomFunc2 = List.map(fun (room : Room) -> if room.Locked then new Room(false, room.Monsters |> monsterFunc2) else room)
let levelFunc2 = List.map(fun (level : Level) -> if level.Illumination < 100 then new Level(level.Illumination, level.Rooms |> roomFunc2) else level)
let dungeon2 = dungeon.Update levelFunc2
dungeon2.Print()
Aquí está el mismo código que usa lentes como se define actualmente en FSharpx. Como señalan otras respuestas, es conveniente usar los registros aquí; Te dan igualdad estructural de forma gratuita entre otras cosas. También adjunto las lentes correspondientes para las propiedades como miembros estáticos; También puede definirlos en un módulo o como funciones sueltas. Prefiero miembros estáticos aquí, por razones prácticas es como un módulo.
open FSharpx
type Monster = {
Awake: bool
} with
static member awake =
{ Get = fun (x: Monster) -> x.Awake
Set = fun v (x: Monster) -> { x with Awake = v } }
type Room = {
Locked: bool
Monsters: Monster list
} with
static member locked =
{ Get = fun (x: Room) -> x.Locked
Set = fun v (x: Room) -> { x with Locked = v } }
static member monsters =
{ Get = fun (x: Room) -> x.Monsters
Set = fun v (x: Room) -> { x with Monsters = v } }
type Level = {
Illumination: int
Rooms: Room list
} with
static member illumination =
{ Get = fun (x: Level) -> x.Illumination
Set = fun v (x: Level) -> { x with Illumination = v } }
static member rooms =
{ Get = fun (x: Level) -> x.Rooms
Set = fun v (x: Level) -> { x with Rooms = v } }
type Dungeon = {
Levels: Level list
} with
static member levels =
{ Get = fun (x: Dungeon) -> x.Levels
Set = fun v (x: Dungeon) -> { x with Levels = v } }
static member print (d: Dungeon) =
d.Levels
|> List.iteri (fun i e ->
printfn "Level %d: Illumination %d" i e.Illumination
e.Rooms |> List.iteri (fun i e ->
let state = if e.Locked then "locked" else "unlocked"
printfn " Room %d is %s" i state
e.Monsters |> List.iteri (fun i e ->
let state = if e.Awake then "awake" else "asleep"
printfn " Monster %d is %s" i state)))
También defino la print como un miembro estático; de nuevo, es como una función en un módulo, y es más componible que un método de instancia (aunque no lo voy a componer aquí).
Ahora para generar los datos de muestra. Creo que { Monster.Awake = true } es más descifrado que el new Monster(true) . Si quisiera usar clases, nombraría el parámetro explícitamente, por ejemplo, Monster(awake: true)
// generate test dungeon
let m1 = { Monster.Awake = true }
let m2 = { Monster.Awake = false }
let m3 = { Monster.Awake = true }
let m4 = { Monster.Awake = false }
let m5 = { Monster.Awake = true }
let m6 = { Monster.Awake = false }
let m7 = { Monster.Awake = true }
let m8 = { Monster.Awake = false }
let r1 = { Room.Locked = true; Monsters = [m1; m2] }
let r2 = { Room.Locked = false; Monsters = [m3; m4] }
let r3 = { Room.Locked = true; Monsters = [m5; m6] }
let r4 = { Room.Locked = false; Monsters = [m7; m8] }
let l1 = { Level.Illumination = 100; Rooms = [r1; r2] }
let l2 = { Level.Illumination = 50; Rooms = [r3; r4] }
let dungeon = { Dungeon.Levels = [l1; l2] }
Dungeon.print dungeon
Ahora viene la parte divertida: componer lentes para actualizar los monstruos de todas las habitaciones para un nivel particular en un calabozo:
open FSharpx.Lens.Operators
let mapMonstersOnLevel nLevel f =
Dungeon.levels >>| Lens.forList nLevel >>| Level.rooms >>| Lens.listMap Room.monsters
|> Lens.update (f |> List.map |> List.map)
// toggle wake status of all monsters
let dungeon1 = dungeon |> mapMonstersOnLevel 0 (Monster.awake.Update not)
Dungeon.print dungeon1
Para la segunda mazmorra también uso lentes pero sin composición de lentes. Es una especie de DSL definido por pequeñas funciones compuestas (algunas de las funciones son de lentes). Tal vez haya lentes para expresar esto de manera más concisa, pero no lo he descubierto.
// remove monsters that are asleep
// which are in locked rooms on levels where illumination < 100
// and unlock those rooms
let unlock = Room.locked.Set false
let removeAsleepMonsters = Room.monsters.Update (List.filter Monster.awake.Get)
let removeAsleepMonsters_unlock_rooms = List.mapIf Room.locked.Get (unlock >> removeAsleepMonsters)
let isLowIllumination = Level.illumination.Get >> ((>)100)
let removeAsleepMonsters_unlock_level = Level.rooms.Update removeAsleepMonsters_unlock_rooms
let removeAsleepMonsters_unlock_levels = List.mapIf isLowIllumination removeAsleepMonsters_unlock_level
let dungeon2 = dungeon |> Dungeon.levels.Update removeAsleepMonsters_unlock_levels
Dungeon.print dungeon2
Usé demasiado las lentes y apunté un poco libremente aquí, parcialmente a propósito, solo para mostrar cómo podría ser. A algunos no les va a gustar, alegando que no es idiomático o claro. Tal vez sea así, pero es otra herramienta que puede elegir usar o no, dependiendo de su contexto.
Pero, lo que es más importante, dado que la actualización es una función seguida por una función seguida de un conjunto, esto no es tan eficiente como su código cuando se trata de procesar listas: una actualización en Lens.forList primero obtiene el elemento nth en la lista, que Es una operación O (n).
Para resumir:
Pros:
- Muy conciso
- Habilita el estilo libre de puntos.
- El código que involucra lentes es generalmente ajeno a la representación del tipo de fuente (puede ser una clase, un registro, un DU de un solo caso, un diccionario, no importa).
Contras:
- Puede ser ineficiente para algunos casos en la implementación actual.
- Debido a la falta de macros, requiere algo de boilerplate.
Gracias por este ejemplo, como resultado, estaré revisando el diseño actual de lentes en FSharpx y veré si se puede optimizar.
Envié este código al repositorio de FSharpx: https://github.com/fsharp/fsharpx/commit/136c763e3529abbf91ad52b8127ce11cbb3dff28
He implementado una biblioteca de lentes en C # a través de la reflexión. El núcleo de la biblioteca es esta función.
/// <summary>
/// Perform an immutable persistent set on a sub
/// property of the object. The object is not
/// mutated rather a copy of the object with
/// the required change is returned.
/// </summary>
/// <typeparam name="ConvertedTo">type of the target object</typeparam>
/// <typeparam name="V">type of the value to be set</typeparam>
/// <param name="This">the target object</param>
/// <param name="names">the list of property names composing the property path</param>
/// <param name="value">the value to assign to the property</param>
/// <returns>A new object with the required change implemented</returns>
private static T Set<T, V>
(this T This, List<string> names, V value)
where T : class, Immutable
{
var name = names.First();
var rest = names.Skip(1).ToList();
if (names.Count == 1)
{
var copy = This.ShallowClone();
copy.SetPrivatePropertyValue(names.First(), value);
return copy as T;
}
else
{
var copy = This.ShallowClone();
var subtree = copy
.GetPrivatePropertyValue<Immutable>(name)
.Set(rest, value);
copy.SetPrivatePropertyValue(names.First(), subtree);
return copy as T;
}
}
La función anterior se compone utilizando la biblioteca auxiliar en varias utilidades, una de las cuales es una pila de deshacer basada en registros persistentes inmutables. Hay una sobrecarga de esta función.
public static Maybe<T> MaybeSet<T,V>
(this T This, Expression<Func<T, V>> prop, V value)
where T : class, Immutable
{
if (!EqualityComparer<V>.Default.Equals(This.Get(prop.Compile()),value))
{
var names = ReactiveUI.Reflection.ExpressionToPropertyNames(prop).ToList();
return This.Set(names, value).ToMaybe();
}
else
{
return None<T>.Default;
}
}
lo que permite una notación segura de tipo más natural usando expresiones LINQ.
foo = foo.Set(f=>f.A.B.C, 10);
Hay una gran cantidad de reflexión en la biblioteca, pero la reducción en la plantilla vale la pena por el impacto en el rendimiento. Ver la especificación. Solo necesito etiquetar el registro como Immutable para que funcione. No tengo que proporcionar getters y settors.
class A : Immutable
{
public int P { get; private set; }
public B B { get; private set; }
public A(int p, B b)
{
P = p;
B = b;
}
}
class B : Immutable
{
public int P { get; private set; }
public C C { get; private set; }
public B(int p, C c)
{
P = p;
C = c;
}
}
class C : Immutable
{
public int P { get; private set; }
public C(int p)
{
P = p;
}
}
namespace Utils.Spec
{
public class ImmutableObjectPatternSpec : IEnableLogger
{
[Fact]
public void SetterSpec()
{
var a = new A
( p:10
, b: new B
( p: 20
, c : new C(30)));
var a_ = a.Set(p => p.B.C.P, 10);
a.Should().NotBe(a_);
a.B.C.P.Should().Be(30);
a_.B.C.P.Should().Be(10);
}
[Fact]
public void StringListGettersShouldWork()
{
var a = new A
( p:10
, b: new B
( p: 20
, c : new C(30)));
var a_ = a.Set(p => p.B.C.P, 10);
a_.Get(p=>p.B.C.P).Should().Be(10);
}
}
}
Quizás las lentes basadas en la reflexión reducirían la placa de la caldera en F #. Tal vez el rendimiento podría mejorarse con el almacenamiento en caché de los accesores o tal vez la generación de IL.
Hice una pregunta similar, pero sobre haskell: ¿Existe un modismo de Haskell para actualizar una estructura de datos anidada?
Las excelentes respuestas mencionan un concepto conocido como lentes funcionales .
Desafortunadamente, no sé qué es el paquete, o si existe, para F #.
Actualización: dos F # -ists expertos (F # -ers? F # as?) Dejaron enlaces útiles sobre esto en los comentarios, así que los publicaré aquí:
¡Es increíble que estos dos muchachos se tomen el tiempo de leer mi respuesta, comentarla y mejorarla, ya que ambos son desarrolladores de FSharpX !
Información más extraña: me motivaron a descubrir cómo hacer esto mediante las assoc-in de assoc-in y update-in Clojure, ¡lo que me demostró que es posible en lenguajes funcionales! Por supuesto, la escritura dinámica de Clojure lo hace más simple que en Haskell / F #. La solución de Haskell consiste en crear plantillas, creo.
No sé por qué quieres usar clases aquí. Creo que puede aprovechar el poder de la coincidencia de patrones si usa registros para almacenar datos y mantenerlos al mínimo:
// Types
type Monster = {
Awake: bool
}
with override x.ToString() =
if x.Awake then "awake" else "asleep"
type Room = {
Locked: bool;
Monsters: Monster list
}
with override x.ToString() =
let state = if x.Locked then "locked" else "unlocked"
state + "/n" + (x.Monsters |> List.mapi (fun i m -> sprintf " Monster %d is %s" i (string m)) |> String.concat "/n")
type Level = {
Illumination : int;
Rooms : Room list
}
with override x.ToString() =
(string x.Illumination) + "/n" + (x.Rooms |> List.mapi (fun i r -> sprintf " Room %d is %s" i (string r)) |> String.concat "/n")
type Dungeon = {
Levels: Level list;
}
with override x.ToString() =
x.Levels |> List.mapi (fun i l -> sprintf "Level %d: Illumination %s" i (string l)) |> String.concat "/n"
Para mí, poner funciones para manipular Dungeon dentro de la clase no es natural. El código se ve mejor si los pones en un módulo y haces uso de las declaraciones anteriores:
/// Utility functions
let updateMonster (m: Monster) a =
{m with Awake = a}
let updateRoom (r: Room) l monstersFunc =
{ Locked = l;
Monsters = r.Monsters |> monstersFunc}
let updateLevel (l: Level) il roomsFunc =
{Illumination = il; Rooms = l.Rooms |> roomsFunc}
let updateDungeon (d: Dungeon) levelsFunc =
{d with Levels = d.Levels |> levelsFunc}
/// Update functions
let mapMonstersOnLevel (d: Dungeon) nLevel =
let monstersFunc = List.map (fun m -> updateMonster m (not m.Awake))
let roomsFunc = List.map (fun r -> updateRoom r r.Locked monstersFunc)
let levelsFunc = List.mapi (fun i l -> if i = nLevel then updateLevel l l.Illumination roomsFunc else l)
updateDungeon d levelsFunc
let removeSleptMonsters (d: Dungeon) =
let monstersFunc = List.filter (fun m -> m.Awake)
let roomsFunc = List.map (fun r -> if r.Locked then updateRoom r false monstersFunc else r)
let levelsFunc = List.map (fun l -> if l.Illumination < 100 then updateLevel l l.Illumination roomsFunc else l)
updateDungeon d levelsFunc
Entonces puedes ver que manipular estas estructuras de datos anidadas es mucho más fácil. Sin embargo, las funciones anteriores todavía tienen redundancia. Puede refactorizar más si usa lentes que vienen muy naturales con los registros. Echa un vistazo this , que está muy cerca de esta formulación.
posted una pregunta similar sobre Scala hace aproximadamente un año. Las respuestas mencionan tres conceptos como una solución a este problema: Cremalleras, Reescritura de árboles y Lentes.