defmodule Dp.Lazy do

  @moduledoc """
  Lazy tailed list

  @author "hanak@emt.bme.hu"
  @date   "$LastChangedDate: 2024-10-07 14:00:10 +0200 (Mon, 07 Oct 2024) $$"
  """

defp sq(x), do: x * x
def sumsq(x, y), do: sq(x) + sq(y)
def f(a), do: sumsq(a+1, a*2)

    
@type lazy_list() :: nil | {any(), (() -> lazy_list())}
# Ez a lista félig lusta: a fej mindig kiértékelődik, a farok lusta

@spec head(xs::lazy_list()) :: x::any()
# Az xs lusta farkú lista feje x
def head({x, _xs}), do: x

@spec tail(xs::lazy_list()) :: ys::lazy_list()
# Az xs lusta farkú lista farka ys
def tail({_x, xs}), do: xs.()

@spec infseq(n::integer()) :: ys::lazy_list()
# Az n-nel kezdődő, egyesével növő egész számok lusta farkú listája ys
def infseq(n), do: {n, fn() -> infseq(n+1) end}

@spec seq(m::integer(), n::integer()) :: ys::lazy_list()
# Az m-től n-ig egyesével növő egész számok lusta farkú listája ys
def seq(m, n) when m <= n, do: {m, fn() -> seq(m+1, n) end}
def seq(_m, _n),           do: nil

@spec cons(ls::[any()]) :: ys::lazy_list()
# Az ls lista elemeiből álló lusta farkú lista ys
def cons([]),     do: nil
def cons([x|xs]), do: {x, fn() -> cons(xs) end}

@spec take(xs::lazy_list(), n::integer()) :: ls::[any()]
# Az xs lusta farkú lista első n eleméből álló lista ls
# Optimalizáljuk n=1-re, hogy ne kelljen a farkát kiértékelni
def take(_,0),       do: []
def take(nil,_),     do: []
def take({x,_}, 1),  do: [x]
def take({x,xs}, n), do: [x|take(xs.(), n-1)]

# # Szószátyár take nyomkövetéshez
# @spec take2(Ys::lazy_list(), N::integer()) :: Ls::list()
# # Az Ys lusta farkú lista első N eleméből álló lista Ls
# take2(L,0), do:
#     io:format("  Hívás (1. klóz): take(~w, 0)~n", [L]),
#     []
# take2(nil,N), do:
#     io:format("  Hívás (2. klóz): take(~w, ~w)~n", [nil, N]),
#     []
# take2({H,T},1), do:
#     io:format("  Hívás (3. klóz): take(~w, ~w)~n", [{H,T}, 1]),
#     [H]
# take2({H,T},N), do:
#     io:format("  Hívás (4. klóz): take(~w, ~w)~n", [{H,T}, N]),
#     [H|take2(T(), N-1)]

# sum/1 és sum/2 csak véges lusta farkú listákra!

@spec sum(xs::lazy_list()) :: n::number()
# Az xs véges lusta farkú számlista elemeinek összege n
def sum(xs), do: sum(xs, 0)

@spec sum(xs::lazy_list(), a::number()) :: n::number()
# Az xs véges lusta farkú számlista elemeinek és az a-nak az összege n
def sum(nil, a), do: a
def sum({x, xs}, a), do: sum(xs.(), x+a)

@spec map(f::((any()) -> any()), ys::lazy_list()) :: zs::lazy_list()
# Az ys elemeiből az f transzformációval előálló lusta farkú lista zs
def map(_, nil),    do: nil
def map(f, {y,ys}), do: {f.(y), fn() -> map(f, ys.()) end}

@spec filter(p::((any()) -> boolean()), ys::lazy_list()) :: zs::lazy_list()
# Az ys p-vel megszűrt elemeiből álló lusta farkú lista a zs
# Kicsit mohó, az eredménylista fejéig kiértékeli a listát
def filter(_, nil),    do: nil
def filter(p, {y, ys}) do
  case p.(y) do
    true ->
      {y, fn() -> filter(p, ys.()) end}
    false ->
      filter(p, ys.()) # Megkeressük az eredmény fejét
  end
end

@spec append(xs::lazy_list(), ys::lazy_list()) :: zs::lazy_list()
# Az xs lusta farkú lista ys (ugyancsak lusta farkú lista) elé
# fűzésével előálló lusta farkú lista zs. Ha xs nem véges, az
# összefűzés felesleges, az ys elemei elérhetetlenek lesznek
def append(nil, ys),    do: ys
def append({x,xs}, ys), do: {x, fn() -> append(xs.(), ys) end}

# # Szószátyár append nyomkövetéshez
# @spec append2(Xs::lazy_list(), Ys::lazy_list()) :: Zs::lazy_list()
# # Az Xs lusta farkú lista Ys (ugyancsak lusta farkú lista) elé fűzésével előálló
# # lusta farkú lista Zs. Ha Xs nem véges, az összefűzés felesleges, az Ys elemei
# # elérhetetlenek lesznek
# append2(nil, Ys), do:
#     io:format("  Hívás (1. klóz): append([], ~w)~n", [(Ys)]),
#     Ys
# append2({H,Ts}, Ys), do:
#     io:format("  Hívás (2. klóz): append(~w, ~w)~n", [([H|Ts]), (Ys)]),
#     {H, fn() -> append2(Ts(), Ys) end}

@spec fibs(curr::integer(), next::integer()) :: ys::lazy_list()
# ys egy olyan általánosított Fibonacci-sorozat (lusta
# farkú lista), amelynek első két tagja curr és next
def fibs(curr, next), do: {curr, fn() -> fibs(next, curr + next) end}

@spec fib(n::integer()) :: f::integer()
# Az n-edik Fibonacci-szám f
def fib(n), do: nth(fibs(0,1), n)

@spec sift(prime::integer(), ys::lazy_list()) :: zs::lazy_list()
# Az ys lusta farkú lista azon elemeinek listája a zs lusta farkú
# lista, melyek nem oszthatók prime-mal
def sift(prime, ys), do: filter(fn(n) -> rem(n, prime) !== 0 end, ys)

@spec sieve(ys::lazy_list()) :: zs::lazy_list()
# A zs lusta farkú lista az ys nem véges lusta farkú
# lista "szitáltja" (üres listára kivételt dob)
def sieve({x,xs}), do: {x, fn() -> sieve(sift(x, xs.())) end}

@spec qsort(ys::lazy_list()) :: zs::lazy_list()
# Az ys lusta farkú lista rendezett változata zs
# Az append alkalmazása: ha csak a lista elejére van
# szükség, csak a lista elejét rendezi
def qsort(nil),         do: nil
# def qsort({pivot, ys}), do:
#     append(qsort(filter(fn(y) -> y < pivot end, ys.())),
#            {pivot, fn() -> qsort(filter(fn(y) -> y >= pivot end, ys.())) end})
def qsort({pivot, ys}) do
  low = fn(x) -> x < pivot end
  high = fn(x) -> x >= pivot end
  append(
    qsort(filter(low, ys.())),
    {pivot,
     fn() -> qsort(filter(high, ys.())) end
    }
  )
end

@spec qsort2(ys::lazy_list()) :: zs::lazy_list()
# Az ys lusta farkú lista rendezett változata zs
# Az append alkalmazása: ha csak a lista elejére van
# szükség, csak a lista elejét rendezi
def qsort2(nil),         do: nil
def qsort2({pivot, ys}), do:
  append(qsort2(filter(&(&1 < pivot), ys.())),
         {pivot,
          fn() -> qsort2(filter(&(&1 >= pivot), ys.()))
	  end}
        )

# import Dp.Lazy  
# qsort2(seq(1,100_000)) |> take(50)

  
# # Szószátyár qsort nyomkövetéshez
# @spec qsort2(Ys::lazy_list()) :: Zs::lazy_list()
# # Az Ys lusta farkú lista rendezett változata a Zs lusta
# # farkú lista
# qsort2(nil), do:
#     nil
# qsort2({Pivot,Ys}), do:
#     io:format(  "Hívás: qsort2(~w)~n", [take({Pivot,Ys}, 100)]),
#     Low = fn(Y) -> Y < Pivot end,
#     High = fn(Y) -> Y >= Pivot end,
#     append2(qsort2(filter(Low, Ys())),
#            {Pivot, fn() -> qsort2(filter(High, Ys())) end})

@spec nth(ys::lazy_list(), n::integer()) :: y::any()
# Az ys lusta lista n-edik eleme y (számozás 0-tól)
def nth({x,_xs}, 0), do: x
def nth({_x,xs}, n), do: nth(xs.(), n-1)

@spec nth2(ys::lazy_list(), n::integer()) :: {:ok, y::any()} | :error
# Az ys lusta lista n-edik eleme y (számozás 0-tól). A visszatérési
# érték az :error atom, ha az ys lista üres, vagy ha n < 0
def nth2({x,_xs}, 0),          do: {:ok, x}
def nth2({_x,xs}, n) when n>0, do: nth2(xs.(), n-1)
def nth2(_, _),                do: :error

def test(1) do
    ys = {1, fn() -> {4, fn() -> {9,fn() -> nil end} end} end}
    [
     sum(seq(1,100000)) === 5000050000,
     sum(cons(Enum.to_list(1..100000))) === 5000050000,
     take(ys, 2) === [1,4],
     take(ys, 3) === [1,4,9],
     take(cons([1,4,9]), 4) === [1,4,9],
     take(seq(1,3),10) === [1,2,3],
     take(infseq(1),10) === [1,2,3,4,5,6,7,8,9,10],
     head(tail(tail(infseq(1)))) === 3,
     take(tail(tail(infseq(1))),1) === [3],
     take(fibs(0,1),10+1) === [0,1,1,2,3,5,8,13,21,34,55],
     nth(fibs(0,1), 100) === 354224848179261915075,
     fib(100) === 354224848179261915075,
     nth2(fibs(0,1), 100) === {:ok,354224848179261915075},
     nth2(nil, 5) === :error,
     nth2(fibs(0,1), -1) === :error,
     take(map(fn(x) -> rem(x, 2) === 0 end, infseq(3)), 3) === [false,true,false],
     take(filter(fn(x) -> rem(x, 2) === 0 end, infseq(3)), 3) === [4,6,8],
     take(filter(fn(x) -> rem(x, 2) === 1 end, seq(3,6)), 3) === [3,5],
     (for i <- 0..4, do: take(append(cons(~c"ab"), cons(~c"12")), i)) ===
	 [[],~c"a",~c"ab",~c"ab1",~c"ab12"],
     take(sieve(infseq(2)), 10) === [2,3,5,7,11,13,17,19,23,29]
    ]
end
def test(2) do
    [
     take(qsort(cons([5,3,6,8,1,7])), 2) === [1,3],
     take(qsort(cons([5,3,6,8,1,7])), 5) === [1,3,5,6,7],
     # io:format("~nTeszthívás: ~s~n", ["take(qsort2(cons([5,3,6,8,1,7])), 2)"]),
     # take(qsort2(cons([5,3,6,8,1,7])), 2) === [1,3],
     # io:format("~nTeszthívás: ~s~n", ["take(qsort2(cons([5,3,6,8,1,7])), 5)"]),
     # take(qsort2(cons([5,3,6,8,1,7])), 5) === [1,3,5,6,7]
    ]
end

# @spec print_mem_usage(String.t()) :: {integer(), non_neg_integer()}
# # Durva becslés: kiírja a függvényhívás előtt és után használt memóriát
# print_mem_usage(Msg) ->
#     {memory,M1} = erlang:process_info(self(), memory),
#     {_,Time} = statistics(runtime),
#     io:format("~16s: ~3w M  |  ~.3f s~n", [Msg, M = M1 div 1024 div 1024, Time / 1000]),
#     {M,Time}
# 
# memtest(1), do:
#     erlang:garbage_collect(),timer:sleep(1000),statistics(runtime),
#     sum(seq(1,10000000)),
#     print_mem_usage("seq o sum")
# memtest(2), do:
#     erlang:garbage_collect(),timer:sleep(1000),statistics(runtime),
#     L = lists:seq(1,10000000),
#     print_mem_usage("lists:seq"),
#     lists:sum(L),
#     print_mem_usage("lists:sum")

end