YES

Problem:
 +(0(),y) -> y
 +(s(x),y) -> s(+(x,y))
 ++(nil(),ys) -> ys
 ++(:(x,xs),ys) -> :(x,++(xs,ys))
 sum(:(x,nil())) -> :(x,nil())
 sum(:(x,:(y,xs))) -> sum(:(+(x,y),xs))
 sum(++(xs,:(x,:(y,ys)))) -> sum(++(xs,sum(:(x,:(y,ys)))))
 -(x,0()) -> x
 -(0(),s(y)) -> 0()
 -(s(x),s(y)) -> -(x,y)
 quot(0(),s(y)) -> 0()
 quot(s(x),s(y)) -> s(quot(-(x,y),s(y)))
 length(nil()) -> 0()
 length(:(x,xs)) -> s(length(xs))
 hd(:(x,xs)) -> x
 avg(xs) -> quot(hd(sum(xs)),length(xs))

Proof:
 DP Processor:
  DPs:
   +#(s(x),y) -> +#(x,y)
   ++#(:(x,xs),ys) -> ++#(xs,ys)
   sum#(:(x,:(y,xs))) -> +#(x,y)
   sum#(:(x,:(y,xs))) -> sum#(:(+(x,y),xs))
   sum#(++(xs,:(x,:(y,ys)))) -> sum#(:(x,:(y,ys)))
   sum#(++(xs,:(x,:(y,ys)))) -> ++#(xs,sum(:(x,:(y,ys))))
   sum#(++(xs,:(x,:(y,ys)))) -> sum#(++(xs,sum(:(x,:(y,ys)))))
   -#(s(x),s(y)) -> -#(x,y)
   quot#(s(x),s(y)) -> -#(x,y)
   quot#(s(x),s(y)) -> quot#(-(x,y),s(y))
   length#(:(x,xs)) -> length#(xs)
   avg#(xs) -> length#(xs)
   avg#(xs) -> sum#(xs)
   avg#(xs) -> hd#(sum(xs))
   avg#(xs) -> quot#(hd(sum(xs)),length(xs))
  TRS:
   +(0(),y) -> y
   +(s(x),y) -> s(+(x,y))
   ++(nil(),ys) -> ys
   ++(:(x,xs),ys) -> :(x,++(xs,ys))
   sum(:(x,nil())) -> :(x,nil())
   sum(:(x,:(y,xs))) -> sum(:(+(x,y),xs))
   sum(++(xs,:(x,:(y,ys)))) -> sum(++(xs,sum(:(x,:(y,ys)))))
   -(x,0()) -> x
   -(0(),s(y)) -> 0()
   -(s(x),s(y)) -> -(x,y)
   quot(0(),s(y)) -> 0()
   quot(s(x),s(y)) -> s(quot(-(x,y),s(y)))
   length(nil()) -> 0()
   length(:(x,xs)) -> s(length(xs))
   hd(:(x,xs)) -> x
   avg(xs) -> quot(hd(sum(xs)),length(xs))
  Usable Rule Processor:
   DPs:
    +#(s(x),y) -> +#(x,y)
    ++#(:(x,xs),ys) -> ++#(xs,ys)
    sum#(:(x,:(y,xs))) -> +#(x,y)
    sum#(:(x,:(y,xs))) -> sum#(:(+(x,y),xs))
    sum#(++(xs,:(x,:(y,ys)))) -> sum#(:(x,:(y,ys)))
    sum#(++(xs,:(x,:(y,ys)))) -> ++#(xs,sum(:(x,:(y,ys))))
    sum#(++(xs,:(x,:(y,ys)))) -> sum#(++(xs,sum(:(x,:(y,ys)))))
    -#(s(x),s(y)) -> -#(x,y)
    quot#(s(x),s(y)) -> -#(x,y)
    quot#(s(x),s(y)) -> quot#(-(x,y),s(y))
    length#(:(x,xs)) -> length#(xs)
    avg#(xs) -> length#(xs)
    avg#(xs) -> sum#(xs)
    avg#(xs) -> hd#(sum(xs))
    avg#(xs) -> quot#(hd(sum(xs)),length(xs))
   TRS:
    +(0(),y) -> y
    +(s(x),y) -> s(+(x,y))
    sum(:(x,:(y,xs))) -> sum(:(+(x,y),xs))
    sum(:(x,nil())) -> :(x,nil())
    ++(nil(),ys) -> ys
    ++(:(x,xs),ys) -> :(x,++(xs,ys))
    -(x,0()) -> x
    -(0(),s(y)) -> 0()
    -(s(x),s(y)) -> -(x,y)
    sum(++(xs,:(x,:(y,ys)))) -> sum(++(xs,sum(:(x,:(y,ys)))))
    length(nil()) -> 0()
    length(:(x,xs)) -> s(length(xs))
    hd(:(x,xs)) -> x
   Matrix Interpretation Processor: dim=2
    
    usable rules:
     +(0(),y) -> y
     +(s(x),y) -> s(+(x,y))
     sum(:(x,:(y,xs))) -> sum(:(+(x,y),xs))
     sum(:(x,nil())) -> :(x,nil())
     ++(nil(),ys) -> ys
     ++(:(x,xs),ys) -> :(x,++(xs,ys))
     -(x,0()) -> x
     -(0(),s(y)) -> 0()
     -(s(x),s(y)) -> -(x,y)
     sum(++(xs,:(x,:(y,ys)))) -> sum(++(xs,sum(:(x,:(y,ys)))))
     length(nil()) -> 0()
     length(:(x,xs)) -> s(length(xs))
     hd(:(x,xs)) -> x
    interpretation:
     [avg#](x0) = [3 1]x0 + [3],
     
     [hd#](x0) = [1 0]x0 + [2],
     
     [length#](x0) = [2 0]x0 + [2],
     
     [quot#](x0, x1) = [2 1]x0,
     
     [-#](x0, x1) = [1 0]x0 + [2],
     
     [sum#](x0) = [1 0]x0,
     
     [++#](x0, x1) = [1 0]x0 + [1 0]x1,
     
     [+#](x0, x1) = [0 1]x0 + [1 0]x1,
     
                [1 0]     [0]
     [hd](x0) = [1 0]x0 + [1],
     
                    [2 0]     [3]
     [length](x0) = [2 0]x0 + [2],
     
                     
     [-](x0, x1) = x0,
     
                 [1 0]  
     [sum](x0) = [0 0]x0,
     
                   [1 1]     [1 0]     [1]
     [:](x0, x1) = [0 0]x0 + [1 0]x1 + [0],
     
                    [2 0]     [2 1]     [1]
     [++](x0, x1) = [2 2]x0 + [2 2]x1 + [0],
     
             [0]
     [nil] = [0],
     
                    [1]
     [s](x0) = x0 + [2],
     
                          
     [+](x0, x1) = x0 + x1,
     
           [2]
     [0] = [0]
    orientation:
     +#(s(x),y) = [0 1]x + [1 0]y + [2] >= [0 1]x + [1 0]y = +#(x,y)
     
     ++#(:(x,xs),ys) = [1 1]x + [1 0]xs + [1 0]ys + [1] >= [1 0]xs + [1 0]ys = ++#(xs,ys)
     
     sum#(:(x,:(y,xs))) = [1 1]x + [1 0]xs + [1 1]y + [2] >= [0 1]x + [1 0]y = +#(x,y)
     
     sum#(:(x,:(y,xs))) = [1 1]x + [1 0]xs + [1 1]y + [2] >= [1 1]x + [1 0]xs + [1 1]y + [1] = sum#(:(+(x,y),xs))
     
     sum#(++(xs,:(x,:(y,ys)))) = [2 2]x + [2 0]xs + [3 3]y + [3 0]ys + [6] >= [1 1]x + [1 1]y + [1 0]ys + [2] = sum#(:(x,:(y,ys)))
     
     sum#(++(xs,:(x,:(y,ys)))) = [2 2]x + [2 0]xs + [3 3]y + [3 0]ys + [6] >= [1 1]x + [1 0]xs + [1 1]y + [1 0]ys + [2] = ++#(xs,sum(:(x,:(y,ys))))
     
     sum#(++(xs,:(x,:(y,ys)))) = [2 2]x + [2 0]xs + [3 3]y + [3 0]ys + [6] >= [2 2]x + [2 0]xs + [2 2]y + [2 0]ys + [5] = sum#(++(xs,sum(:(x,:(y,ys)))))
     
     -#(s(x),s(y)) = [1 0]x + [3] >= [1 0]x + [2] = -#(x,y)
     
     quot#(s(x),s(y)) = [2 1]x + [4] >= [1 0]x + [2] = -#(x,y)
     
     quot#(s(x),s(y)) = [2 1]x + [4] >= [2 1]x = quot#(-(x,y),s(y))
     
     length#(:(x,xs)) = [2 2]x + [2 0]xs + [4] >= [2 0]xs + [2] = length#(xs)
     
     avg#(xs) = [3 1]xs + [3] >= [2 0]xs + [2] = length#(xs)
     
     avg#(xs) = [3 1]xs + [3] >= [1 0]xs = sum#(xs)
     
     avg#(xs) = [3 1]xs + [3] >= [1 0]xs + [2] = hd#(sum(xs))
     
     avg#(xs) = [3 1]xs + [3] >= [3 0]xs + [1] = quot#(hd(sum(xs)),length(xs))
     
                    [2]         
     +(0(),y) = y + [0] >= y = y
     
                         [1]            [1]            
     +(s(x),y) = x + y + [2] >= x + y + [2] = s(+(x,y))
     
                         [1 1]    [1 0]     [1 1]    [2]    [1 1]    [1 0]     [1 1]    [1]                    
     sum(:(x,:(y,xs))) = [0 0]x + [0 0]xs + [0 0]y + [0] >= [0 0]x + [0 0]xs + [0 0]y + [0] = sum(:(+(x,y),xs))
     
                       [1 1]    [1]    [1 1]    [1]             
     sum(:(x,nil())) = [0 0]x + [0] >= [0 0]x + [0] = :(x,nil())
     
                    [2 1]     [1]           
     ++(nil(),ys) = [2 2]ys + [0] >= ys = ys
     
                      [2 2]    [2 0]     [2 1]     [3]    [1 1]    [2 0]     [2 1]     [2]                 
     ++(:(x,xs),ys) = [2 2]x + [4 0]xs + [2 2]ys + [2] >= [0 0]x + [2 0]xs + [2 1]ys + [1] = :(x,++(xs,ys))
     
                          
     -(x,0()) = x >= x = x
     
                   [2]    [2]      
     -(0(),s(y)) = [0] >= [0] = 0()
     
                        [1]              
     -(s(x),s(y)) = x + [2] >= x = -(x,y)
     
                                [2 2]    [2 0]     [3 3]    [3 0]     [6]    [2 2]    [2 0]     [2 2]    [2 0]     [5]                                
     sum(++(xs,:(x,:(y,ys)))) = [0 0]x + [0 0]xs + [0 0]y + [0 0]ys + [0] >= [0 0]x + [0 0]xs + [0 0]y + [0 0]ys + [0] = sum(++(xs,sum(:(x,:(y,ys)))))
     
                     [3]    [2]      
     length(nil()) = [2] >= [0] = 0()
     
                       [2 2]    [2 0]     [5]    [2 0]     [4]                
     length(:(x,xs)) = [2 2]x + [2 0]xs + [4] >= [2 0]xs + [4] = s(length(xs))
     
                   [1 1]    [1 0]     [1]         
     hd(:(x,xs)) = [1 1]x + [1 0]xs + [2] >= x = x
    problem:
     DPs:
      
     TRS:
      +(0(),y) -> y
      +(s(x),y) -> s(+(x,y))
      sum(:(x,:(y,xs))) -> sum(:(+(x,y),xs))
      sum(:(x,nil())) -> :(x,nil())
      ++(nil(),ys) -> ys
      ++(:(x,xs),ys) -> :(x,++(xs,ys))
      -(x,0()) -> x
      -(0(),s(y)) -> 0()
      -(s(x),s(y)) -> -(x,y)
      sum(++(xs,:(x,:(y,ys)))) -> sum(++(xs,sum(:(x,:(y,ys)))))
      length(nil()) -> 0()
      length(:(x,xs)) -> s(length(xs))
      hd(:(x,xs)) -> x
    Qed